poj 2425 博弈 SG函数
hdu 1573

poj 1228 凸包

scturtle posted @ 2010年9月17日 04:40 in algorithm , 2319 阅读

题意给出一个凸包,问是否唯一。若某边上仅有由两个点,则易见可以加一个点扩充,形成另一个凸包。对数据无语。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int sig(double d) { return fabs(d) < 1E-6 ? 0 : d < 0 ? -1 : 1; }
struct Point{double x,y;
	bool operator < (const Point &p) const {
		return sig(x-p.x) != 0 ? x < p.x : sig(y-p.y) < 0;
	}
};
double dis(Point a, Point b) {
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cross(Point o, Point a, Point b) {
	return (a.x - o.x)*(b.y - o.y)-(b.x - o.x)*(a.y - o.y);
}
int graham(Point*p, int n, int*ch) {
#define push(x)     ch[len ++]=x
#define pop()		len --
sort(p, p+n);
	int len = 0, len0 = 1, i;
	for(i = 0; i < n; i ++) {
		while(len > len0 && sig(cross(p[ch[len-1]], p[ch[len-2]], p[i]))<=0)
			pop();
		push(i);
	}
	len0 = len;
	for(i = n-2; i >= 0; i --) {
		while(len > len0 && sig(cross(p[ch[len-1]], p[ch[len-2]], p[i]))<=0)
			pop();
		push(i);
	}
	return len-1;
}


#define maxn 1001
Point p[maxn]; 
int ch[maxn];
bool flag[maxn];
int flag2[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int cas,i,j,n,m;
    scanf("%d",&cas);
    bool ok;
    while(cas--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        m=graham(p,n,ch);
        if(n<=5) {puts("NO");continue;}//加了这句才过……
        memset(flag,0,sizeof(flag));
        memset(flag2,0,sizeof(flag2));
        for(i=0;i<m;i++)
            flag[ch[i]]=1;
        for(i=0;i<n;i++) if(!flag[i])
        {
            for(j=1;j<m;j++)
                if(sig(cross(p[i],p[ch[j-1]],p[ch[j]]))==0)
                {flag2[j-1]|=2;flag2[j]|=1;}
            if(sig(cross(p[i],p[ch[m-1]],p[ch[0]]))==0)
            {flag2[m-1]|=2;flag2[0]|=1;}
        }
        ok=1;
        for(i=0;i<m;i++)
            if(flag2[i]<3) {ok=0;break;}
        if(ok)
            puts("YES");
        else
            puts("NO");
    }
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter