1 条题解

  • 0
    @ 2025-7-17 22:43:05
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    const int mx = 60;
    using namespace std;
    typedef struct poi{
      double x;
      double y;
      poi(double a = 0, double b = 0){
      	x = a; y = b;
      }
      
      poi operator + (const poi a) const{
       	return poi(x+a.x, y+a.y);
      }
      
      poi operator - (const poi a) const{
      	return poi(x-a.x, y-a.y);
      }
      
      double operator * (const poi a) const{
      	return (x*a.x + y*a.y);
      }
      
      poi operator * (const  double a) const{
      	return poi(x*a , y*a);                              //这里重载错了直接爆炸一直wa,逗号写成加号 
      }
      
      double operator ^(const poi a) const{
      	return(x*a.y - y*a.x);
      }
      
    }vec;
    poi P[mx], S[mx*10], T[mx*10];
    int n;
     
    int dbcmp(double a){
    	return fabs(a)<(1e-6)?0:(a>0?1:-1);
    }
     
    poi getline(poi p, vec v, poi q, vec w){
    	vec u = p - q;
    	double t = (w^u)/(v^w);
    	return p+v*t;
    }
     
    bool judge(){
    	for(int i = 0; i < n; i++){
    		S[i] = P[i];
    	}
    	int num1 = n, add;
    	
    	for(int i = 0; i < n; i++){
    		 add = 0;
    		for(int j = 0; j < num1; j++){ 
    			int ans1 = dbcmp((P[(i+1)%n]-P[i]) ^ (S[j]-P[i]));
    			int ans2 = dbcmp((P[(i+1)%n]-P[i]) ^ (S[(j+1)%num1]-P[i]));
    			
    			if(ans1 >= 0)
    			   T[add++] = S[j];
    			if(ans1 * ans2 < 0)
    			   T[add++] = getline(P[i], (P[(i+1)%n]-P[i]), S[j], (S[(j+1)%num1]-S[j]));
    		} 
    		
    		for(int k = 0; k < add; k++){
    			S[k] = T[k];
    		}
    		num1 = add;
    	}
    	
    	return num1 != 0;
    }
     
    int main(){
    	while(scanf("%d",&n) && n){
    	
    		for(int i = 0; i < n; i++){
    			scanf("%lf%lf", &P[i].x, &P[i].y);
    		}
    		
    		if(judge()) puts("1");
    		else puts("0"); 
    	}
    	
    	return 0;
    }
    • 1

    信息

    ID
    2131
    时间
    5000ms
    内存
    64MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者