首页 > 代码库 > POJ 3130

POJ 3130

这题,加了精度错了,不加精度反而对了。。。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN=110;const double eps=1e-8; struct point {    double x,y;};point pts[MAXN],p[MAXN],q[MAXN];int n,cCnt,curCnt; int DB(double d){    if(d>eps) return 1;    if(d<-eps) return -1;    return 0;} void initial(){    for(int i=1;i<=n;i++)    p[i]=pts[i];    p[n+1]=p[1];    p[0]=p[n];    cCnt=n;} void getline(point x,point y,double &a,double &b,double &c){    a = y.y - x.y;    b = x.x - y.x;    c = y.x * x.y - x.x * y.y;} point intersect(point x,point y,double a,double b,double c){    double u = fabs(a * x.x + b * x.y + c);    double v = fabs(a * y.x + b * y.y + c);    point pt;    pt.x=(x.x * v + y.x * u) / (u + v);    pt.y=(x.y * v + y.y * u) / (u + v);    return  pt;} void cut(double a,double b,double c){    curCnt=0;    for(int i=1;i<=cCnt;i++){        if(a*p[i].x+b*p[i].y+c <=0) q[++curCnt] = p[i];        else {            if(a*p[i-1].x + b*p[i-1].y + c <=0){                q[++curCnt] = intersect(p[i],p[i-1],a,b,c);            }             if(a*p[i+1].x + b*p[i+1].y + c <=0){                q[++curCnt] = intersect(p[i],p[i+1],a,b,c);            }        }    }    for(int i = 1; i <= curCnt; ++i)p[i] = q[i];    p[curCnt+1] = q[1];p[0] = p[curCnt];    cCnt = curCnt;} void slove(){    initial();    for(int i=1;i<=n;i++){        double a,b,c;        getline(pts[i],pts[i+1],a,b,c);        cut(a,b,c);    }} int main(){    while(true){        scanf("%d",&n);        if(n==0) break;        for(int i=1;i<=n;i++)        scanf("%lf%lf",&pts[i].x,&pts[i].y);        pts[n+1]=pts[1];        slove();        if(cCnt>=1) printf("1\n");        else printf("0\n");    }    return 0;}