| ||||||||||
| 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:求大神指点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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator