[poj] 3384 Feng Shui || 半平面交

原题

给出两个圆的半径，将两个圆放在多边形内，求能占的最大面积（可以重叠但不可以越过边界），求两圆的圆心所在的位置.

---

用半平面交将多边形每个边向内推进R然后枚举各个点之间最大距离即为两圆的圆心坐标
半平面交：http://blog.csdn.net/accry/article/details/6070621

#include<cstdio>
#include<cstring>
#include<cmath>
#define N 110
using namespace std;
int n,r,endcnt,tmpcnt;
double A,B,C;
struct point
{
    double x,y;
    double norm()
	{
	    return sqrt(x*x+y*y);
	}
}a[N],p[N],q[N];

double ABS(double x)
{
    return x>=0?x:-x;
}

void init()
{
    for (int i=1;i<=n;i++)
	p[i]=a[i];
    p[n+1]=p[1];
    p[0]=p[n];
    endcnt=n;
}

double dist(point p1,point p2)
{
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

void getline(point p1,point p2,double &a,double &b,double &c)
{
    a=p2.y-p1.y;
    b=p1.x-p2.x;
    c=p2.x*p1.y-p2.y*p1.x;
}

point getinter(point p1,point p2,double a,double b,double c)
{
    double u=ABS(a*p1.x+b*p1.y+c);
    double v=ABS(a*p2.x+b*p2.y+c);
    point tmp;
    tmp.x=(v*p1.x+u*p2.x)/(u+v);
    tmp.y=(v*p1.y+u*p2.y)/(u+v);
    return tmp;
}

void cut(double a,double b,double c)
{
    tmpcnt=0;
    for (int i=1;i<=endcnt;i++)
	if (a*p[i].x+b*p[i].y+c>=0)
	    q[++tmpcnt]=p[i];
	else
	{
	    if (a*p[i-1].x+b*p[i-1].y+c>0)
		q[++tmpcnt]=getinter(p[i],p[i-1],a,b,c);
	    if (a*p[i+1].x+b*p[i+1].y+c>0)
		q[++tmpcnt]=getinter(p[i],p[i+1],a,b,c);
	}
    for (int i=1;i<=tmpcnt;i++)
	p[i]=q[i];
    p[tmpcnt+1]=p[1];
    p[0]=p[tmpcnt];
    endcnt=tmpcnt;
}

int main()
{
    scanf("%d%d",&n,&r);
    for (int i=1;i<=n;i++)
	scanf("%lf%lf",&a[i].x,&a[i].y);
    a[n+1]=a[1];
    init();
    for (int i=1;i<=n;i++)
    {
	point u,v,w;
	w.x=a[i+1].y-a[i].y;
	w.y=a[i].x-a[i+1].x;
	double k=r*1.0/w.norm();
	w.x*=k;
	w.y*=k;
	u.x=a[i].x+w.x;
	u.y=a[i].y+w.y;
	v.x=a[i+1].x+w.x;
	v.y=a[i+1].y+w.y;
	getline(u,v,A,B,C);
	cut(A,B,C);
    }
    double mx=-1;
    int r1,r2;
    for (int i=1;i<=endcnt;i++)
	for (int j=i+1;j<=endcnt;j++)
	{
	    double tmp=dist(p[i],p[j]);
	    if (tmp>mx)
	    {
		mx=tmp;
		r1=i;
		r2=j;
	    }
	}
    printf("%f %f %f %f
",p[r1].x,p[r1].y,p[r2].x,p[r2].y);
    return 0;
}