# 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;
}

# hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

### 输出

5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5

2 1 3 2

# LeetCode Valid Triangle Number

LeetCode Valid Triangle Number Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:
1. The length of the given array won’t exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

# LeetCode Valid Square

LeetCode Valid Square Given the coordinates of four points in 2D space, return whether the four points could construct a square. The coordinate (x,y) of a point is represented by an integer array with two integers. Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

Note:
1. All the input integers are in the range [-10000, 10000].
2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
3. Input points have no order.

p3------p4
|       |
|       |
p1------p2


# LeetCode Rectangle Area

223. Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Example:

Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

Note:

Assume that the total area is never beyond the maximum possible value of int.

class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H)
{
int area = (C – A) * (D – B) + (G – E) * (H – F);
if (E >= C || // 右
H <= B || // 下
G <= A || // 左
F >= D) // 上
return area;
return area – (min(C, G) – max(A, E)) * (min(D, H) – max(B, F));
}
};

typedef long long ll;
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
ll area1 = (C - A)*(D - B);
ll area2 = (G - E)*(H - F);
ll area3 = 0;
if (E >= C || F >= D || G <= A || H <= B) {
//没有重叠
}
else {
int ae = max(A, E), cg = min(C, G);
int bf = max(B, F), dh = min(D, H);
area3 = abs(cg - ae)*abs(dh - bf);
}
return area1 + area2 - area3;
}
};


# hihoCoder 1040-矩形判断

hihoCoder 1040-矩形判断 #1040 : 矩形判断 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 给出平面上4条线段，判断这4条线段是否恰好围成一个面积大于0的矩形。 输入 输入第一行是一个整数T(1<=T<=100)，代表测试数据的数量。 每组数据包含4行，每行包含4个整数x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 100000)；其中(x1, y1), (x2,y2)代表一条线段的两个端点。 输出 每组数据输出一行YES或者NO，表示输入的4条线段是否恰好围成矩形。 样例输入 3 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1 2 3 1 0 3 2 3 2 2 3 1 0 0 1 0 1 1 0 1 0 2 0 2 0 1 1 1 1 0 1 样例输出 YES YES NO