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 201141843309 at 2012-09-24 16:49:26 on Problem 1228
In Reply To:求大神指点 Posted by:nofalpc at 2012-06-15 23:05:20
> #include<iostream>
> #include<stdio.h>
> #include<cmath>
> #include<algorithm>
> 
> using namespace std;
> 
> const double eps=1e-8;
> const int maxn=1000+10;
> const double maxx=2e10;
> const double pi=acos(-1.0);
> int top;
> 
> struct point{  
>     //平面上的点 
>     int x;
>     int y;
>     point(int x0=0,int y0=0)  
>     {  
>         //构造 
>         x=x0;
>         y=y0;
>     }    
>     
>     point operator -(point b)          
>     {
>         //减    表示向量AB=A-B,实际运算B-A;
>         return point(b.x-x,b.y-y);
>     }
>     
>     int operator %(point b)        
>     {
>         //叉积 
>         return x*b.y-y*b.x;
>     }
> }Null;
> 
> 
> point yd(0,0);
> int st[maxn];
> point pp[maxn];
> int n1;
> point pt;
> int pnum;
> 
> double dist(point p1,point p2)
> {
>     double px,py;
>     px=p1.x-p2.x;
>     py=p1.y-p2.y;
>     return sqrt(px*px+py*py);
> }
> 
> bool operator <(const point a,const point b)
> {
>     int m=(pp[0]-a)%(pp[0]-b);
>     if(m>0)
>     {
>         return true;
>     }
>     else if(m==0&&(dist(pp[0],a)>dist(pp[0],b)))
>     {
>         return true;
>     }
>     return false;
> }
> 
> void graham(int n)     
> {
>     //三个以上的点集,以排序按Y-X 
>     top=2;
>     st[0]=0;
>     st[1]=1;
>     st[2]=2;
>     int i;
>     for(i=2;i<=n;i++)
>     {
>         while((pp[st[top-1]]-pp[st[top]])%(pp[i]-pp[st[top-1]])>=0)
>         {
>             if(top==0)break;
>             top--;
>         }
>         top++;
>         st[top]=i; 
>     }
>     return ;
> }
> 
> void init()
> {
>     int i;
>     pt.y=-1;
>     for(i=0;i<n1;i++)
>     {
>         scanf("%d %d",&pp[i].x,&pp[i].y);
>         if(pt.y==-1||pp[i].y<pt.y)
>         {
>             pt=pp[i];
>             pnum=i;
>         }
>         if(pp[i].y==pt.y&&pp[i].x<pt.x)
>         {
>             pt=pp[i];
>             pnum=i;
>         }
>     }    
>     swap(pp[pnum],pp[0]);
>     sort(pp+1,pp+n1);
>     pp[n1]=pp[0];
>     return ;
> }
> 
> void work(int n)
> {
> 	bool ok=true;
> 	if(top<2)
> 	{
> 		ok=false;
> 	}
> 	int i;
> 	for(i=2;i<top;i++)
> 	{
> 		if(st[i]-st[i-1]==1)
> 		{
> 			ok=false;
> 			break;
> 		}
> 	}
> 	if(i==top&&fabs((pp[n-1]-pp[n-2])%(pp[n-1]-pp[n]))>eps)
> 	{
> 		ok=false;
> 	}
> 	if(ok)
> 	{
> 		printf("YES\n");
> 	}
> 	else
> 	{
> 		printf("NO\n");
> 	}
> 	return ;
> }
> int main()
> {
> 	int t;
> 	scanf("%d",&t);
>     while(t--)
>     {
> 		scanf("%d",&n1);
>         init();
>         if(n1<6)
>         {
> 			printf("NO\n");
> 		}
> 		else
> 		{
>         	graham(n1);
>         	work(n1);
> 		}
>     }
>     //system("pause");
>     return 0;
> }

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