1 条题解
-
0
#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
- 上传者