POJ 3384 Feng Shui 凸包直径 + 半平面交

G++一直没有过了换成 C++果断A掉了。。。It's time to bet RP.

题意：给一个多边形，然后放进去两个圆，让两个圆的覆盖面积尽量最大，输出两个圆心的坐标。

思路：将多边形的边向里平移圆的的半径R，然后求新多边形的距离最长的两个点。

平移多少废了一点脑筋，其他的就都是现成的模板了。

这个是平移的函数，自己想得，不知道还有没有更简便的。左右平移只需要改一下向量 V

void Panning_Edge(P &a1,P &a2,double dis)
{
    //向v的右侧平移
    P v = {a2.y-a1.y,a1.x-a2.x};

    double t = dis/Cal_Point_Dis(a1,a2);

    a1.x = a1.x+v.x * t;
    a1.y = a1.y+v.y * t;

    a2.x = a2.x+v.x*t;
    a2.y = a2.y+v.y*t;
}

PS：好吧，我承认自己没想出，然后翻了别人的题解。。。。这个内推边真的用的好巧哇

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string>

#define LL long long
#define EPS (1e-9)
#define Right 1;
#define Left -1;

using namespace std;

struct P
{
    double x,y;
} p[55],tp[2510],cp[2510];

double X_Mul(P a1,P a2,P b1,P b2)
{
    P v1 = {a2.x-a1.x,a2.y-a1.y},v2 = {b2.x-b1.x,b2.y-b1.y};
    return v1.x*v2.y - v1.y*v2.x;
}

P Cal_Cross_Position(P a1,P a2,P b1,P b2)
{
    double t = fabs(X_Mul(a1,a2,a1,b1))/fabs(X_Mul(a1,a2,b2,b1));
    P p = {b1.x + (b2.x-b1.x)*t,b1.y + (b2.y-b1.y)*t};
    return p;
}

double Cal_Point_Dis(P a1,P a2)
{
    return sqrt((a2.x-a1.x)*(a2.x-a1.x) + (a2.y-a1.y)*(a2.y-a1.y));
}

void Panning_Edge(P &a1,P &a2,double dis)
{
    //向v的右侧平移
    P v = {a2.y-a1.y,a1.x-a2.x};

    double t = dis/Cal_Point_Dis(a1,a2);

    a1.x = a1.x+v.x * t;
    a1.y = a1.y+v.y * t;

    a2.x = a2.x+v.x*t;
    a2.y = a2.y+v.y*t;
}

int Cut_Polygon(P a1,P a2,P *tp,int n,P *cp,double rad)
{
    Panning_Edge(a1,a2,rad);

    double xm1,xm2;
    int i ,top = 0;
    for(i = 0;i < n; ++i)
    {
        xm1 = X_Mul(a1,a2,a1,tp[i]),xm2 = X_Mul(a1,a2,a1,tp[i+1]);
        if(xm1 < EPS && xm2 < EPS)
        {
            cp[top++] = tp[i];
        }
        else if(xm1 < EPS || xm2 < EPS)
        {
            if(xm1 < EPS)
            {
                cp[top++] = tp[i];
            }
            cp[top++] = Cal_Cross_Position(a1,a2,tp[i],tp[i+1]);
        }
    }
    cp[top] = cp[0];
    return top;
}

void Cal_Center_Position(P *tp,P *cp,P *p,int n,double rad)
{
    int i,j,top;

    for(i = 0;i <= n; ++i)
    {
        tp[i] = p[i];
    }

    for(top = n,i = 0;i < n; ++i)
    {
        top = Cut_Polygon(p[i],p[i+1],tp,top,cp,rad);
        for(j = 0;j <= top; ++j)
        {
            tp[j] = cp[j];
        }
        //点集内有重点
    }

   //求凸包的直径  鉴于点集不是很大   也懒得写旋转卡壳了

   double TempDis,MaxDis = -1;
   int s1,s2;

   for(i = 0;i <= top; ++i)
   {
       for(j = 0;j <= top; ++j)
       {
           TempDis = Cal_Point_Dis(tp[i],tp[j]);
           if(MaxDis < TempDis)
           {
               MaxDis = TempDis,s1 = i,s2 = j;
           }
       }
   }

   //最终答案
   printf("%.4lf %.4lf %.4lf %.4lf
",tp[s1].x,tp[s1].y,tp[s2].x,tp[s2].y);

}

int main()
{
    int i,n;
    double rad;
    while(scanf("%d %lf",&n,&rad) != EOF)
    {
        for(i = 0; i < n; ++i)
        {
            scanf("%lf %lf",&p[i].x,&p[i].y);
        }

        p[n] = p[0];

        Cal_Center_Position(tp,cp,p,n,rad);
    }
    return 0;
}