http://codeforces.com/gym/102219/problem/H
Are You Safe?
time limit per test
15.0 s
memory limit per test
256 MB
input
standard input
output
standard output
Recently, the nation was shocked by news of Sungai Kim Kim incident in Pasir Gudang, Johor, which has been polluted by chemical waste. Thousands of people who are affected had experienced nausea, dizziness and vomiting, and more than 100 schools were ordered to shut. In order to ensure that such incident will not happen again, an early warning system need o be developed so that residents can make early preparation, and authorities are able to move and act much faster.
A group of scientists has formed a committee to handle the incident, and a smart system with Internet of Things (IoT) sensors was suggested. Numerous sensors which can sense and monitor damages to the environment, either air or water, have been strategically installed around the state, and their coordinates are also recorded. However, the proposed system encountered a failure during its first testing phase. They want you to fix the problem in determining whether the given coordinates of sensors are safe or in the affected areas.
An affected area is defined as the polygon with the minimum length perimeter that can enclose all sensors that trigger warning signal within that area. For example, the sensors (represented by dots) of an affected area and its associated polygon, as well as safe (represented by triangles) and unsafe (represented by diamonds) points of the first dataset are illustrated below.
Input
The input will contain records of data for several test cases of affected areas. The first line of each data set contains a non-negative integer TT, the number of test cases (1≤T≤50).(1≤T≤50). Each test case starts with two non-negative integer CC and PP which is the number of coordinates (3≤C≤50)(3≤C≤50), and points (1≤P≤50)(1≤P≤50), respectively. The next CC lines contain coordinates (x-coordinate, y-coordinate) of each installed sensor, separated with blank spaces. The following PP lines contain coordinates (x-coordinate, y-coordinate) of certain locations in the state, separated with blank spaces. All coordinates are integers between −500−500 and 500500 inclusive.
Output
For each test case, output the following item:
First line: The number of the test cases. The first record corresponds to Case1Case1, the second to Case2Case2 , etc.
Next line: A listing of all the points that appear on the perimeter of the affected area. The points must be identified in the standard form "x-coordinate y- coordinate". The listing must be oriented counter-clockwise and begin and end with the same point.
Last line: For each point of location in the data set, output the line:
x−coordinatey−coordinateisstatusx−coordinatey−coordinateisstatus
where x−coordinatey−coordinatex−coordinatey−coordinate is the coordinate of the location from the input and statusstatus is ′safe′′safe′ or ′unsafe′′unsafe′. A location is considered unsafe it is within the sensor perimeter. A point in exactly at the edge of the perimeter is considered safe.
Each test case must be separated by an empty line. See example.
Example
input
Copy
2 6 5 -477 -180 31 -266 -474 28 147 49 323 -53 277 -79 346 488 -139 -183 -427 129 386 -222 -408 -315 5 2 -52 -325 104 420 315 356 -192 8 493 146 404 228 -239 484
output
Copy
Case 1 -477 -180 31 -266 323 -53 147 49 -474 28 -477 -180 346 488 is safe! -139 -183 is unsafe! -427 129 is safe! 386 -222 is safe! -408 -315 is safe! Case 2 -192 8 -52 -325 493 146 315 356 104 420 -192 8 404 228 is unsafe! -239 484 is safe!
题意是给你n个点，求最少长度的围栏把他们全部围起来，然后输出围栏上的点，
然后再给你m个点，这m个点是否在围栏里面，是的话输出unsafe，否则输出safe
裸的凸包，然后根据面积判断这个点是否在围栏里面
关于凸包：https://blog.csdn.net/qq_41431457/article/details/98635632
如果这个点在里面，这个点跟围栏上任意相邻的两个点组成的三角形面积之和就等于凸包的面积，
如果在外面，就大于凸包的面积，
这题精度有点问题，ＷＡ了一发，0.5的大小都给忽略了，估计是精确到整数吧
给了15秒，有点膨胀。。。然而我只跑了60ms
#include<bits/stdc++.h>
using namespace std;
const int M = 55;
int n, m, T, ac = 1;
double all = 0.0;
struct point
{
double x, y;
point() {}
point(double x, double y) :x(x),y(y){}
// {this->x=x, this->y=y;}
point operator + (point t) { return point(x+t.x, y+t.y); }
point operator - (point t) { return point(x-t.x, y-t.y); }
bool operator == (point t) { return x == t.x && y == t.y;}
bool operator < (const point &t) const
{
if(x != t.x) return x < t.x;
return y < t.y;
}
};
point a[M], b[M], c[M];//a存放所有的点，b存放凸包上的点
double cross(point a, point b)//叉积
{
return a.x*b.y - a.y*b.x;
}
double distance(point a, point b)//求两点之间的距离
{
return hypot(a.x - b.x, a.y - b.y);
}
double area(point a, point b, point c)//求三个点组成的三角形面积
{
//S=√[p(p-a)(p-b)(p-c)] p=(a+b+c)/2;
double e = distance(a,b);
double f = distance(a,c);
double g = distance(b,c);
double p = (e+f+g) / 2.0;
return sqrt(p*(p-e)*(p-f)*(p-g));
}
int slove(int n)//求凸包，安德鲁算法
{
sort(a, a+n);
n = unique(a, a+n) - a;
//求下凸包
int v = 0;
for(int i = 0; i < n; i++)
{
while(v > 1 && cross(b[v-1] - b[v-2], a[i] - b[v-2]) <= 0.0) v--;
b[v++] = a[i];
}
//求上凸包
int j = v;
for(int i = n-2; i >= 0; i--)
{
while(v > j && cross(b[v-1] - b[v-2], a[i] - b[v-2]) <= 0.0) v--;
b[v++] = a[i];
}
return n > 1 ? v-1 : v;//v是b里面的顶点数
}
bool check(point x, int k)//判断x这个 点是否在凸包中
{
double my = 0.0;
for(int i = 1; i < k; i++)
my += area(x, b[i], b[i-1]);
my += area(x, b[k-1], b[0]);
// cout << endl << "fuck " << my << ' ' <<all << ' ';
// printf("%.10lf %.10lf", my - all, my);
// cout << endl;
if(fabs(my - all) < 0.9) return true;//精度注意
return false;
}
void print(int k)
{
for(int i = 0; i < k; i++)
cout << b[i].x << ' ' << b[i].y << endl;
cout << b[0].x << ' ' << b[0].y << endl;
}
int main()
{
cin >> T;
while(T--)
{
all = 0.0;
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> a[i].x >> a[i].y;
int k = slove(n);
for(int i = 2; i < k; i++)
all += area(b[0], b[i-1], b[i]);
for(int i = 0; i < m; i++)
cin >> c[i].x >> c[i].y;
cout << "Case " << ac++ <<endl;
print(k);
for(int i = 0; i < m; i++)
{
point x = c[i];
cout << x.x << ' ' << x.y;
if(check(x,k))
cout << " is unsafe!" << endl;
else
cout << " is safe!" << endl;
}
cout << endl;
}
return 0;
}