程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3384 Feng Shui 半平面交

poj3384 Feng Shui 半平面交

編輯：C++入門知識

//題意:用兩個圓去覆蓋一個多邊形，求最多覆蓋面積時兩個圓的圓心（按一定順序）。
//多邊形向內推進r求半平面交 + 最遠點對
//這裡的數據不夠大，可以用暴力求最遠點對 94ms AC，代碼如下：

[cpp]
#include<iostream>
#include<cstdio>
#include<math.h>
#define eps 1e-8
//using namespace std;
const int MAXN=202;
struct point{double x,y;};
point points[MAXN],p[MAXN],q[MAXN];
int n;
double r;
bool zero(double x)
{
    return x>0? x<eps:x>-eps;
}
double xmult(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int same_side(point p1,point p2,point l1,point l2)
{
    return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
point intersection(point p1,point p2,point p3,point p4)
{
    point ret=p1;
    double t=((p1.x-p3.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p3.y))
        /((p1.x-p2.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p2.y));
    ret.x+=t*(p2.x-p1.x);
    ret.y+=t*(p2.y-p1.y);
    return ret;
}
void polygon_cut(int &n,point *p,point l1,point l2,point side)
{
    point pp[1000];
    int m=0,i;
    for(i=0;i<n;i++)
    {
        if(same_side(p[i],side,l1,l2))
            pp[m++]=p[i];
        if(!same_side(p[i],p[(i+1)%n],l1,l2)
            &&!(zero(xmult(p[i],l1,l2))
            &&zero(xmult(p[(i+1)%n],l1,l2))))
            pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2);
    }
    n=0;
    for(i=0;i<m;i++)
        if(!i||!zero(pp[i].x-pp[i-1].x)||!zero(pp[i].y-pp[i-1].y))
            p[n++]=pp[i];
        if(zero(p[n-1].x-p[0].x)&&zero(p[n-1].y-p[0].y))
            n--;//
        // if(n<3)n=0;
}
double distance(point p1,point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void slove(double dis,int &m)
{
    int i;
    for(i=0;i<n;i++)p[i]=points[i];
    for(i=0;i<n;i++)
    {
        point side;
        point s=points[i],e=points[(i+1)%n];
        double xx=s.x-e.x,yy=s.y-e.y;
        double dd=sqrt(xx*xx+yy*yy);
        s.x+=dis*(-yy)/dd;
        s.y+=dis*(xx)/dd;
        e.x+=dis*(-yy)/dd;
        e.y+=dis*(xx)/dd;
        side.x=s.x-yy;
        side.y=s.y+xx;
        polygon_cut(m,p,s,e,side);
    }
}
int main()
{

    while(scanf("%d%lf",&n,&r)!=EOF)
    {
        int i,j;
        for(i=0;i<n;i++)
            scanf("%lf%lf",&points[i].x,&points[i].y);
        int m=n;
        slove(r,m);
        // for(i=0;i<m;i++)printf("%lf,%lf\n",p[i].x,p[i].y);
        double dis=0;
        int s=0,e=0;
        for(i=0;i<m;i++)
        {
            for(j=0;j<m;j++)
                if(i!=j)
                {
                    double temp=distance(p[i],p[j]);
                    if(temp-dis>eps)
                    {
                        dis=temp;
                        s=i;e=j;
                    }
                }
        }
        if(p[s].x-p[e].x>eps||zero(p[s].x-p[e].x)&&p[s].y>-p[e].y>eps)
        {
            point tt=p[s];
            p[s]=p[e];
            p[e]=tt;
        }

        printf("%.10lf %.10lf %.10lf %.10lf\n",p[s].x,p[s].y,p[e].x,p[e].y);
    }
    return 0;
}