/*
题意：顺时针给你n个点地板，然后你用两个一样圆形地毯（半径为R）覆盖一个多边形地板，求这两个地毯最多能覆盖多边形的面积此时的两圆的圆心坐标
此题用半平面交将多边形的每条边一起向“内”推进R，得到新的多边形，然后求多边形的最远两点（这两点即是两圆圆心）
另外注意：此题要精确4位小数，所以程序计算的样例得出的结果和题目上的结果不一样
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
const int INF=0x7fffffff;
const double eps=1e-8;
const double PI=acos(-1.0);
const double inf=1e5;
const int Max=2001;
#define zero(x) (((x)>0?(x):-(x))<eps)
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int sign(double x)
{
    return (x>eps)-(x<-eps);
}
typedef struct Node
{
    double x;
    double y;
    Node(const double &_x=0, const double &_y=0) : x(_x), y(_y) {}
    void input()
    {
        cin>>x>>y;
    }
    void output()
    {
        cout<<x<<" "<<y<<endl;
    }
}point;
point list[Max],stack[Max];
point qq[Max],pp[Max],pnt[Max];
int n;
int top;

int cnt;
int curcnt;
double xmult(point p0,point p1,point p2)
{
	return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Distance(point p1,point p2)// 返回两点之间欧氏距离
{
	return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );
}
bool cmp(point p1,point p2)
{
    double temp;
    temp=xmult(list[0],p1,p2);
    if(temp>0)
        return true;
    if(temp==0&&(Distance(list[0],p1)<Distance(list[0],p2)))
        return true;
    return false;
}
void Init(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {
        pp[i]=pnt[i];
    }
    pp[n+1]=pnt[1];
    pp[0]=pnt[n];
    cnt=n;
}
void GetLine(point u,point v,double &a,double &b,double &c)
{
    a=v.y-u.y;
    b=u.x-v.x;
    c=v.x*u.y-u.x*v.y;
}
point Intersect(point u,point v,double a,double b,double c)
{
    double q=fabs(a*u.x+b*u.y+c);
    double p=fabs(a*v.x+b*v.y+c);
    point res;
    res.x=((p*u.x+q*v.x)/(q+p));
    res.y=((p*u.y+q*v.y)/(q+p));
    return res;
}
void CutLine(double a,double b,double c)
{
    int i;
    curcnt=0;
    for(i=1;i<=cnt;i++)
    {
        if(sign(a*pp[i].x+b*pp[i].y+c)>=0)
        {
            qq[++curcnt]=pp[i];
        }
        else
        {
            if(sign(a*pp[i-1].x+b*pp[i-1].y+c)>0)
            {
                qq[++curcnt]=Intersect(pp[i],pp[i-1],a,b,c);
            }
            if(sign(a*pp[i+1].x+b*pp[i+1].y+c)>0)
            {
                qq[++curcnt]=Intersect(pp[i],pp[i+1],a,b,c);
            }
        }
    }
    for(i=1;i<=curcnt;i++)
    {
        pp[i]=qq[i];
    }
    pp[curcnt+1]=pp[1];
    pp[0]=pp[curcnt];
    cnt=curcnt;
}
bool solve(double r)//多边形每条边向内推进r距离得到新的多边形
{
    Init(n);
    int i;
    double kk,a,b,c;
    point ta,tb,tt;
    for(i=1;i<=n;i++)
    {
        tt.x=pnt[i+1].y-pnt[i].y;
        tt.y=pnt[i].x-pnt[i+1].x;
        kk=r/sqrt(tt.x*tt.x+tt.y*tt.y);
        tt.x=tt.x*kk;
        tt.y=tt.y*kk;
        ta.x=pnt[i].x+tt.x;
        ta.y=pnt[i].y+tt.y;
        tb.x=pnt[i+1].x+tt.x;
        tb.y=pnt[i+1].y+tt.y;
        GetLine(ta,tb,a,b,c);
        CutLine(a,b,c);
    }
    if(cnt<=0)
        return false;
    return true;
}
int main()
{
    int m,i,j;
    int ra,rb;
    double r;
    double maxn,temp;
    while(cin>>n>>r)
    {
        for(i=1;i<=n;i++)
            pnt[i].input();
        pnt[n+1]=pnt[1];
        //Init(n);
        solve(r);
        ra=0;
        rb=0;
        maxn=-99999;
        for(i=1;i<=cnt;i++)
        {
            for(j=i+1;j<=cnt;j++)
            {
                temp=Distance(pp[i],pp[j]);
                if(temp>maxn)
                {
                    maxn=temp;
                    ra=i;
                    rb=j;
                }
            }
        }
        cout<<setprecision(4)<<setiosflags(ios::fixed)<<pp[ra].x<<" "<<pp[ra].y<<" "<<pp[rb].x<<" "<<pp[rb].y<<endl;
    }
    return 0;
}
/*
5 2
-2 0
-5 3
0 8
7 3
5 0

4 3
0 0
0 8
10 8
10 0


*/

• Re:我会说我一遍AC了吗=。= (3) kakaluoter 2016-07-31 14:47:08