# HDOJ 1007-Quoit Design

HDOJ 1007-Quoit Design

# Quoit Design

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 77740    Accepted Submission(s): 20729

Problem DescriptionHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.

Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

InputThe input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input

2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

Sample Output

0.71
0.00
0.75

AuthorCHEN, Yue
SourceZJCPC2004
RecommendJGShining   |   We have carefully selected several similar problems for you:  10061009100510081004

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

struct Point
{
double x_, y_;
Point() :x_(0), y_(0) {};
Point(double x, double y) :x_(x), y_(y) {};
};

bool CmpX(const Point &p1, const Point &p2) {
return p1.x_ < p2.x_;
}

bool CmpY(const Point &p1, const Point &p2) {
return p1.y_ < p2.y_;
}

// 暂时只算距离平方，最后开平方根
double CalDist(const Point &p1, const Point &p2) {
return (p1.x_ - p2.x_)*(p1.x_ - p2.x_) + (p1.y_ - p2.y_)*(p1.y_ - p2.y_);
}

double CalMinDist(vector<Point> &data, int l, int r) {

if (r - l == 2) {
return CalDist(data[l], data[l + 1]);
}
else if (r - l == 3) {
double d1 = CalDist(data[l], data[l + 1]);
double d2 = CalDist(data[l], data[l + 2]);
double d3 = CalDist(data[l + 1], data[l + 2]);
return min(min(d1, d2), d3);
}

int m = l + (r - l) / 2;
int mx = data[m].x_;
double dd = min(CalMinDist(data, l, m), CalMinDist(data, m, r));
double d = sqrt(dd);

vector<Point> rect;
for (int i = l; i < r; ++i) {
if (data[i].x_ > mx - d && data[i].x_ < mx + d) {
rect.push_back(data[i]);
}
}

sort(rect.begin(), rect.end(), CmpY);
for (int i = 0; i < rect.size(); ++i) {
for (int j = i + 1; j < rect.size(); ++j) {
double tmpd = CalDist(rect[i], rect[j]);
if (tmpd > dd)break;
dd = min(dd, tmpd);
}
}

return dd;
}

int main() {
freopen("input.txt", "r", stdin);

int n;
while (scanf("%d", &n)) {
if (n == 0)break;
vector<Point> data(n, Point());
for (int i = 0; i < n; ++i) {
scanf("%lf %lf", &data[i].x_, &data[i].y_);
}
sort(data.begin(), data.end(), CmpX);
printf("%.2lf\n", sqrt(CalMinDist(data, 0, data.size())) / 2);
}

return 0;
}

# HDOJ 1159-Common Subsequence

HDOJ 1159-Common Subsequence

# Common Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 59402    Accepted Submission(s): 27503

Problem DescriptionA subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, …, xm> another sequence Z = <z1, z2, …, zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, …, ik> of indices of X such that for all j = 1,2,…,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc abfcab
programming contest
abcd mnp

Sample Output

4
2
0

SourceSoutheastern Europe 2003
RecommendIgnatius   |   We have carefully selected several similar problems for you:  10871176100310581069

#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int lcs(const string& a, const string& b)
{
int n = a.size(), m = b.size();
if (n == 0 || m == 0)
return 0;
vector<int> dp(m + 1, 0);
for (int i = 1; i <= n; ++i) {
int pre = 0;
for (int j = 1; j <= m; ++j) {
int cur = 0;
if (a[i – 1] == b[j – 1])
cur = pre + 1;
else
cur = max(dp[j – 1], dp[j]);
pre = dp[j];
dp[j] = cur;
}
}
return dp[m]; // 最大值就是右下角的值
}
void construct_lcs(vector<vector<int> >& direction, const string& a, int i, int j, string& lcs)
{
if (i == 0 || j == 0)
return;
if (direction[i][j] == 3) {
construct_lcs(direction, a, i – 1, j – 1, lcs);
lcs += string(1, a[i – 1]); // direction下标1对应a下标0，所以i-1
}
else if (direction[i][j] == 2) {
construct_lcs(direction, a, i – 1, j, lcs);
}
else {
construct_lcs(direction, a, i, j – 1, lcs);
}
}
string lcs_string(const string& a, const string& b)
{
int n = a.size(), m = b.size();
if (n == 0 || m == 0)
return 0;
vector<int> dp(m + 1, 0);
vector<vector<int> > direction(n + 1, vector<int>(m + 1, 0)); // 1:left,2:up,3:diagonal
for (int i = 1; i <= n; ++i) {
int pre = 0;
for (int j = 1; j <= m; ++j) {
int cur = 0;
if (a[i – 1] == b[j – 1]) {
cur = pre + 1;
direction[i][j] = 3;
}
else {
if (dp[j – 1] > dp[j]) {
cur = dp[j – 1];
direction[i][j] = 1;
}
else {
cur = dp[j];
direction[i][j] = 2;
}
}
pre = dp[j];
dp[j] = cur;
}
}
string ans;
construct_lcs(direction, a, n, m, ans); // 从右下角递归往前找，LCRS P225
return ans;
}
int main()
{
//freopen("input.txt", "r", stdin);
string a, b;
while (cin >> a >> b) {
cout << lcs(a, b) << endl;
//cout << lcs(a, b) << "\t" << lcs_string(a, b) << endl;;
}
return 0;
}

# HDOJ 5424-Rikka with Graph II

HDOJ 5424-Rikka with Graph II Rikka with Graph II Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 379 Accepted Submission(s): 94 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path. It is too difficult for Rikka. Can you help her? Input There are no more than 100 testcases. For each testcase, the first line contains a number n(1≤n≤1000). Then n lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. Output For each testcase, if there exist a Hamiltonian path print “YES” , otherwise print “NO”. Sample Input 4 1 1 1 2 2 3 2 4 3 1 2 2 3 3 1 Sample Output NO YES Hint For the second testcase, One of the path is 1->2->3 If you doesn’t know what is Hamiltonian path, click here (https://en.wikipedia.org/wiki/Hamiltonian_path). Source BestCoder Round #53 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

# HDOJ 5422-Rikka with Graph

HDOJ 5422-Rikka with Graph Rikka with Graph Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 144 Accepted Submission(s): 72 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Yuta has a non-direct graph with n vertices and m edges. The length of each edge is 1. Now he wants to add exactly an edge which connects two different vertices and minimize the length of the shortest path between vertice 1 and vertice n. Now he wants to know the minimal length of the shortest path and the number of the ways of adding this edge. It is too difficult for Rikka. Can you help her? Input There are no more than 100 testcases. For each testcase, the first line contains two numbers n,m(2≤n≤100,0≤m≤100). Then m lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. There may be multiedges and self loops. Output For each testcase, print a single line contains two numbers: The length of the shortest path between vertice 1 and vertice n and the number of the ways of adding this edge. Sample Input 2 1 1 2 Sample Output 1 1 Hint You can only add an edge between 1 and 2. Source BestCoder Round #53 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

# HDOJ 3535-AreYouBusy

HDOJ 3535-AreYouBusy AreYouBusy Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3450 Accepted Submission(s): 1342 Problem Description Happy New Term! As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad. What’s more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as “jobs”. A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs).So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss’s advice)? Input There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0<m<=100), there are m jobs in this set , and the set type is s, (0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 , and 2 for the one you can choose freely).then m pairs of integers ci,gi follows (0<=ci,gi<=100), means the ith job cost ci minutes to finish and gi points of happiness can be gained by finishing it. One job can be done only once. Output One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 . Sample Input 3 3 2 1 2 5 3 8 2 0 1 0 2 1 3 2 4 3 2 1 1 1 3 4 2 1 2 5 3 8 2 0 1 1 2 8 3 2 4 4 2 1 1 1 1 1 1 0 2 1 5 3 2 0 1 0 2 1 2 0 2 2 1 1 2 0 3 2 2 1 2 1 1 5 2 8 3 2 3 8 4 9 5 10 Sample Output 5 13 -1 -1 Author hphp Source 2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU Recommend zhouzeyong | We have carefully selected several similar problems for you: 3033 1712 3449 2639 2159

# HDOJ 5418-Victor and World

HDOJ 5418-Victor and World Victor and World Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others) Total Submission(s): 643 Accepted Submission(s): 268 Problem Description After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are n countries on the earth, which are numbered from 1 to n. They are connected by m undirected flights, detailedly the i-th flight connects the ui-th and the vi-th country, and it will cost Victor’s airplane wi L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country. Victor now is at the country whose number is 1, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country. Input The first line of the input contains an integer T, denoting the number of test cases. In every test case, there are two integers n and m in the first line, denoting the number of the countries and the number of the flights. Then there are m lines, each line contains three integers ui, vi and wi, describing a flight. 1≤T≤20. 1≤n≤16. 1≤m≤100000. 1≤wi≤100. 1≤ui,vi≤n. Output Your program should print T lines : the i-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel. Sample Input 1 3 2 1 2 2 1 3 3 Sample Output 10 Source BestCoder Round #52 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5416 5415

# HDOJ 5417-Victor and Machine

HDOJ 5417-Victor and Machine Victor and Machine Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 177 Accepted Submission(s): 91 Problem Description Victor has a machine. When the machine starts up, it will pop out a ball immediately. After that, the machine will pop out a ball every w seconds. However, the machine has some flaws, every time after x seconds of process the machine has to turn off for y seconds for maintenance work. At the second the machine will be shut down, it may pop out a ball. And while it’s off, the machine will pop out no ball before the machine restart. Now, at the 0 second, the machine opens for the first time. Victor wants to know when the n-th ball will be popped out. Could you tell him? Input The input contains several test cases, at most 100 cases. Each line has four integers x, y, w and n. Their meanings are shown above。 1≤x,y,w,n≤100. Output For each test case, you should output a line contains a number indicates the time when the n-th ball will be popped out. Sample Input 2 3 3 3 98 76 54 32 10 9 8 100 Sample Output 10 2664 939 Source BestCoder Round #52 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5418 5416

# HDOJ 5392-Infoplane in Tina Town

HDOJ 5392-Infoplane in Tina Town Infoplane in Tina Town Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 1636 Accepted Submission(s): 385 Problem Description There is a big stone with smooth surface in Tina Town. When people go towards it, the stone surface will be lighted and show its usage. This stone was a legacy and also the center of Tina Town’s calculation and control system. also, it can display events in Tina Town and contents that pedestrians are interested in, and it can be used as public computer. It makes people’s life more convenient (especially for who forget to take a device). Tina and Town were playing a game on this stone. First, a permutation of numbers from 1 to n were displayed on the stone. Town exchanged some numbers randomly and Town recorded this process by macros. Town asked Tine,”Do you know how many times it need to turn these numbers into the original permutation by executing this macro? Tina didn’t know the answer so she asked you to find out the answer for her. Since the answer may be very large, you only need to output the answer modulo 3∗230+1=3221225473 (a prime). Input The first line is an integer T representing the number of test cases. T≤5 For each test case, the first line is an integer n representing the length of permutation. n≤3∗106 The second line contains n integers representing a permutation A1…An. It is guaranteed that numbers are different each other and all Ai satisfies ( 1≤Ai≤n ). Output For each test case, print a number ans representing the answer. Sample Input 2 3 1 3 2 6 2 3 4 5 6 1 Sample Output 2 6 Source BestCoder Round #51 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5390 5389

# HDOJ 5391-Zball in Tina Town

HDOJ 5391-Zball in Tina Town Zball in Tina Town Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 817 Accepted Submission(s): 471 Problem Description Tina Town is a friendly place. People there care about each other. Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day, it becomes 1 time as large as its original size. On the second day,it will become 2 times as large as the size on the first day. On the n-th day,it will become n times as large as the size on the (n-1)-th day. Tina want to know its size on the (n-1)-th day modulo n. Input The first line of input contains an integer T, representing the number of cases. The following T lines, each line contains an integer n, according to the description. T≤$$10^5$$,2≤n≤$$10^9$$ Output For each test case, output an integer representing the answer. Sample Input 2 3 10 Sample Output 2 Source BestCoder Round #51 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5392 5390

On the n-th day,it will become n times as large as the size on the (n-1)-th day.