H. Are You Safe? Convex hull naked problem

subject link

Ideas

Find convex hull
Whether the judgment point is in the convex hull
Note the order of the output convex hull Graham The algorithm will be more convenient

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
template <typename T>
inline void read(T &s){
    s = 0;T w = 1, ch = getchar();while (!isdigit(ch)) {
     if (ch == '-') w = -1; ch = getchar(); }while (isdigit(ch))  {
     s = (s << 1) + (s << 3) + (ch ^48); ch = getchar();} s *= w;}
template <typename T>
inline void write(T s){
    if (s < 0) putchar('-'), s = -s;if (s > 9) write(s / 10);putchar(s % 10 + '0');}
#define int long long
#define endl "\n"
#define _orz ios::sync_with_stdio(false),cin.tie(0)
#define mem(str,num) memset(str,num,sizeof(str))
#define forr(i,a,b) for(int i = a; i <= b;i++)
#define forn(i,n) for(int i = 0; i < n; i++)
#define dbug() cout <<"0k!"<< endl;
#define lg __lg
typedef long long ll;
int pri[16] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
const int inf = 0x3f3f3f3f;
const int INF = ~0ULL;
const int N = 1e6+10;
const double eps = 1e-8;
const double Dinf = 1e18;
const double pi = acos(-1.0);

// Judge positive and negative 
int sgn(double x){
    
    if(fabs(x) < eps) return 0;
    if(x > 0) return 1; //  Positive numbers 
    return -1;
}
// double  Compare the size 
int dcmp(double x, double y){
    
    if(fabs(x - y) < eps)
        return 0;
    if(x > y)
        return 1;
    return -1;
}

// Point class 
struct Point{
    
    double x,y;
    Point(double x = 0,double y = 0):x(x),y(y){
     } //  Constructors 
    bool operator < (const Point&B)const{
    return x < B.x || x == B.x && y < B.y;}
};
typedef Point Vector;
// After the vector translation, it's still the same vector , So you just need the origin and the end of the vector 
//! vector  +  vector  =  vector , spot  +  vector  =  vector 
// Overloading vector operators  + - * / < ==
Vector operator + (Vector A , Vector B) {
    return Vector{
    A.x+B.x,A.y+B.y};}
Vector operator - (Point A , Point B) {
    return Vector{
    A.x-B.x,A.y-B.y};} 
Vector operator * (Point A , double p) {
    return Vector{
    A.x*p,A.y*p};} //  Number multiplication 
Vector operator / (Point A , double p) {
    return Vector{
    A.x/p,A.y/p};}
//! spot / Vector comparison function 
// It can be used to find the bottom left point 
// bool operator < (Point &A,Point&B){return A.x < B.x || A.x == B.x && A.y < B.y;}
bool operator == (const Point &a ,const Point& b) {
    return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
//  Return radian system 
double Polar_angle(Vector A){
    return atan2(A.y,A.x);}
//  Dot product   The relationship between the included angle and the dot product 
double Dot(Vector A,Vector B){
    return A.x*B.x+A.y*B.y;}
//  Cross product 
double Cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;}
//  spot  c  Is it in a vector ab Left side 
bool ToLeftTest(Point a,Point b,Point c){
    return Cross(b-a,c-a) >= 0;}
double Length(Vector A) {
    return sqrt(Dot(A,A));}
double Angle(Vector A,Vector B) {
    return acos(Dot(A,B)/Length(A)/Length(B));}
//! Three points determine two vectors ,( Intersection point for A Two vectors of AB and AC) Then find the cross product of these two vectors ( Cross riding )
double Area2(Point A,Point B,Point C){
    return Cross(B-A,C-A);}
//  The vector after the vector rotates counterclockwise 
Vector Rotate(Vector A,double rad){
    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}


int c,p;
Point pt[55];
Point ask[55];

int stk[1005];
int top;
int cnt = 0;
bool cmp(Point a,Point b){
    
    double t = Cross(a-pt[1],b-pt[1]);
    if(sgn(t) > 0) return true;
    if(sgn(t) == 0 && dcmp(Length(a-pt[1]),Length(b-pt[1])) < 0) return true;
    return false;
 }

void Graham(){
    
    top = 0;
    sort(pt+1,pt+1+c);
    sort(pt+2,pt+1+c,cmp); 
    stk[++top] = 1,stk[++top] = 2;
    forr(i,3,c){
    
        while(top >=2 && sgn(Cross(pt[stk[top]]-pt[stk[top-1]],pt[i] - pt[stk[top-1]])) <= 0) top--; // <  Collinear join convex hull 
        stk[++top] = i;
    }
    stk[++top] = 1;
}

bool check(int i){
    

    forr(j,1,top-1){
    
        Vector t =  pt[stk[j+1]] - pt[stk[j]];
        Vector w  = ask[i] - pt[stk[j]];
        if(sgn(Cross(t,w)) < 0) return true;
    }
    return false;
}

void print(){
    
    forr(i,1,top) cout << pt[stk[i]].x <<" "<< pt[stk[i]].y << endl;
}
void solve(){
    
    cin>>c>>p;
    forr(i,1,c) cin>>pt[i].x >> pt[i].y;
    forr(i,1,p) cin >> ask[i].x >> ask[i].y;

    Graham();

    printf("Case %d\n",++cnt);
    print();
    forr(i,1,p){
    
        if (check(i)) printf("%.0f %.0f is safe!\n",ask[i].x,ask[i].y);
        else printf("%.0f %.0f is unsafe!\n",ask[i].x,ask[i].y);
    }
    cout << endl;
}

signed main()
{
    
    int t;cin>>t;
    while(t--) solve();
    return 0;
}