题目链接:http://codeforces.com/gym/102219/problem/H
Time limit per test 15.0 s Memory limit per test 256 MB

Description

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 T, the number of test cases (1≤T≤50). Each test case starts with two non-negative integer C and P which is the number of coordinates (3≤C≤50), and points (1≤P≤50), respectively. The next C lines contain coordinates (x-coordinate, y-coordinate) of each installed sensor, separated with blank spaces. The following P lines contain coordinates (x-coordinate, y-coordinate) of certain locations in the state, separated with blank spaces. All coordinates are integers between −500 and 500 inclusive.

Output

For each test case, output the following item:

First line: The number of the test cases. The first record corresponds to Case1, the second to Case2 , 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−coordinateisstatus

where x−coordinatey−coordinate is the coordinate of the location from the input and status is ′safe′or ′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

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

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!

Problem solving report:

Description: 给你n个点，求最少长度的围栏把他们全部围起来，然后输出围栏上的点，然后再给你m个点，这m个点是否在围栏里面，是的话输出unsafe，否则输出safe
Problem solving: 裸的凸包，然后根据面积判断这个点是否在围栏里面就行了。

Accepted Code:

//AndrewScan
/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const double eps = 1e-8;
typedef struct Point {
    double x, y;
    Point(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}
    bool operator < (const Point& s) const {
        return x != s.x ? x < s.x : y < s.y;
    }
}vect;
struct Point p[MAXN], S[MAXN], s;
int sgn(double x) {
    return x < -eps ? -1 : x > eps ? 1 : 0;
}
vect operator - (const Point a, const Point b) {
    return vect(a.x - b.x, a.y - b.y);
}
double Cross(const vect a, const vect b) {
    return a.x * b.y - a.y * b.x;
}
double dist(const Point a, const Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool Onleft(const Point a, const Point b, const Point c) {
    return sgn(Cross(b - a, c - a)) > 0;
}
bool InTB(const Point p[], const Point s, int n) {
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        if (Cross(p[j] - p[i], s - p[i]) <= 0)
            return false;
    }
    return true;
}
int AndrewScan(Point p[], int n) {
    sort(p, p + n);
    int top = 0;
    for (int i = 0; i < n; i++) {
        while (top > 1 && !Onleft(S[top - 2], S[top - 1], p[i]))
            top--;
        S[top++] = p[i];
    }
    int tmp = top;
    for (int i = n - 2; i >= 0; i--) {
        while (top > tmp && !Onleft(S[top - 2], S[top - 1], p[i]))
            top--;
        S[top++] = p[i];
    }
    return top;
}
int main() {
    int n, q, t, cnt, kase = 0;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &q);
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        cnt = AndrewScan(p, n);
        if (n > 1)
            cnt--;
        if (kase)
            printf("\n");
        printf("Case %d\n", ++kase);
        for (int i = 0; i < cnt; i++)
            printf("%.0lf %.0lf\n", S[i].x, S[i].y);
        printf("%.0lf %.0lf\n", S[0].x, S[0].y);
        while (q--) {
            scanf("%lf%lf", &s.x, &s.y);
            printf("%.0lf %.0lf ", s.x, s.y);
            if (InTB(S, s, cnt))
                printf("is unsafe!\n");
            else printf("is safe!\n");
        }
    }
    return 0;
}