| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么re#include<cstdio>
#include<algorithm>
using namespace std;
#define N 210
struct xing;
struct point
{
int x,y;
point(){}
point(int _x,int _y) {x=_x;y=_y;}
friend point operator +(const point &p1,const point &p2)
{
return (point){p1.x+p2.x,p1.y+p2.y};
}
friend point operator -(const point &p1,const point &p2)
{
return (point){p1.x-p2.x,p1.y-p2.y};
}
friend point operator *(int k,const point &p)
{
return (point){p.x*k,p.y*k};
}
friend int operator *(const point &p1,const point &p2)
{
return p1.x*p2.y-p1.y*p2.x;
}
friend point jiao(const point &p1,const point &v1,const point &p2,const point &v2)
{
return p1+((p2-p1)*v2)/(v1*v2)*v1;
}
}x,k;
xing *q;
struct xing
{
int n,i;
point qa[N],*p=qa+1;
int area()
{
int ans=0;
for(i=0;i<n;++i) ans+=p[i]*p[i+1];
return ans;
}
void init()
{scanf("%d",&n);
for(i=0;i<n;++i) scanf("%d%d",&p[i].x,&p[i].y);
p[n]=p[0];
if(area()<0) reverse(p,p+n+1);
}
void push(const point &x)
{
p[n++]=x;
}
int cha(const point &p)
{
return k*(p-x);
}
void cut()
{
q->n=0;
p[-1]=p[n-1];p[n]=p[0];
for (i=0;i<n;++i)
{
if(cha(p[i])>=0) q->push(p[i]); else
{
if(cha(p[i-1])>0) q->push(jiao(p[i],p[i-1]-p[i],x,k));
if(cha(p[i+1])>0) q->push(jiao(p[i],p[i+1]-p[i],x,k));
}
}
(*this)=*q;
}
}g0,g;
int main()
{
q=new xing;
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int tt,i;scanf("%d",&tt);
while (tt--)
{
g0.init();g=g0;
for(i=0;i<g0.n;++i)
{
x=g0.p[i];k=g0.p[i+1]-x;
g.cut();
}
if(g.n) puts("YES");
else puts("NO");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator