Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么re

Posted by kczno1 at 2017-03-05 23:03:11 on Problem 3335
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator