CodeForce-Aree You Safe?(凸包&判定点は凸包内)

テーマリンク:http://codeforces.com/gym/102219/problem/HTime limit per test 15.0 s Memory limit per test 256 MB
Description
Recently,the nation was shaked by news of Sugai Kim Kim incident in Pasir Gdang,Johor,which has been polluted by chemical waste.Thousads of people whoararaffected had had eexperinininininininininindededededededededededededededededededededededededededededededededededededededededededededededededededededeststststststststinininininininininininininindedededededededededededededededededededededededededehappen again,an early warning system need o be developed so that redents can make early preparation、and authorities are able to move and act much faster.
A group of scientists has formed a comittee to hande the incident、and a smart ssysstem with Internet of Thininins(IoT)sensors sugggted.Numerous sensorwhich can sense and moniitor damageter the the thethethethethe virerereininininininininininininininininininininininininaaaaatotototototoststststststststrererererererererererererererererererererererererererererererererererererererererererererereded.However,the proposed system encountered a failure during its first testing phase.The y want you to fix the problem in determining whethe the given coordinansors of sensors are are the affected ars.
An affected ara is defined as the polygon with the minimum length perimetetetaaaaaaaaaaaaaaaaaaaffecteted araaaththththinaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaatetetetes(rererererererereesented bybybybydedededededededeaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaesented by diamonds)points of the first dataset are illustrated below.

 
Input
The input will contain records of data for several test cases of affected aras.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 coordination (3≦C≦50)、and points (1≦P≦50)、respively.The next C ラインcontain coordination(x-coordinate、y-coordinate)of each installed sensor、separated with blank spaces.The follwing P ラインcontain coordination(x-coordinate、y-coordinate)of certain locations in the state、separated with blank spaces.All coordinase are e e e between −500 and 500 inclusive.
Output
For each test case,output the following item:
First line:The number of the test cases.The first recordponds to Case 1,the second to Case 2 , etc.
Next line:A listing of all the points that appar on the perimeter of the affected ara.The points must be identified in the standard form「x-coordinate-coordinate」.The listing must ored orted counter-clockine and
Last line:For each point of location in the data set,output the line:
x−coordinary−coordination tatus
where x−coordinary−coordinate is the coordinate of the location from the input and status is ′safe’or ′unsafe’.A location is consided unsafe it is within the sensor perimeter.A point in exactly at the edge of the perimeter is consideded safe.
Each test case must be separated by an empty line.See example.
Example
input
2 6 5-477-180 31-266-474 147 323-53 277-79 488-139-183-427 129 386-222-408-315 2-52-325 4 356-192 8 493 146-239 484
out put
Case 1-477-180 31-266 323-53 147 49-474-477-180 346-488 is safe!-139-183 is unsafe!-427 is safe 129386-222 is safe!-408-315 is safe
Case 2-192 8-52-325 493 146 315 356 420-192 8 404 228 is unsafe!-239 484 is safe
Problem soving report:
Description: n個のポイントをあげます.最小長さのフェンスで彼らを全部囲み、フェンス上のポイントを出力して、m個のポイントをあげます.このm個の点はフェンスの中にありますか?そうでないとunsafeを出力します.さもなければsafeProblem sovingを出力します. 裸の凸包は面積によってこの点がフェンスの中にあるかどうかを判断すればいいです.
Acceepted Code:

//AndrewScan
/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include 
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("
");
        printf("Case %d
", ++kase);
        for (int i = 0; i < cnt; i++)
            printf("%.0lf %.0lf
", S[i].x, S[i].y);
        printf("%.0lf %.0lf
", 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!
");
            else printf("is safe!
");
        }
    }
    return 0;
}