POJ 3384 Feng Shui(半平面交向内推进求最远点对)

题目链接

题意 : 两个圆能够覆盖的最大多边形面积的时候两个圆圆心的坐标是多少,两个圆必须在多边形内。

思路 : 向内推进r,然后求多边形最远的两个点就是能覆盖的最大面积。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream> using namespace std ; struct node
{
double x,y ;
}p[],temp[],newp[];
int n,newn ;
double a,b,c,r ; void getlinee(node x,node y)
{
a = y.y-x.y ;
b = x.x-y.x ;
c = y.x*x.y-x.x*y.y ;
}
node intersect(node x,node y)
{
double u = fabs(a*x.x+b*x.y+c) ;
double v = fabs(a*y.x+b*y.y+c) ;
node t ;
t.x = (x.x*v+y.x*u)/(u+v) ;
t.y = (x.y*v+y.y*u)/(u+v) ;
return t ;
}
void cut()
{
int cutn = ;
for(int i = ; i <= newn ; i++)
{
if(newp[i].x*a+newp[i].y*b+c >= )
temp[++cutn] = newp[i] ;
else
{
if(newp[i-].x*a+newp[i-].y*b+c > )
temp[++cutn] = intersect(newp[i-],newp[i]) ;
if(newp[i+].x*a+newp[i+].y*b+c > )
temp[++cutn] = intersect(newp[i+],newp[i]) ;
}
}
for(int i = ; i <= cutn ; i++)
newp[i] = temp[i] ;
newp[cutn+] = newp[] ;
newp[] = newp[cutn] ;
newn = cutn ;
//printf("newn%d = %d\n",cnt++,newn) ;
}
void solve()
{
for(int i = ; i <= n ; i ++)
{
newp[i] = p[i] ;
}
newp[n+] = p[] ;
newp[] = p[n] ;
newn = n ;
for(int i = ; i <= n ; i++)
{
node t,t1,t2 ;
t.x = p[i+].y-p[i].y ;
t.y = p[i].x-p[i+].x ;
double k = r/sqrt(t.x*t.x+t.y*t.y) ;
t.x *= k ;
t.y *= k ;
t1.x = t.x+p[i].x ;
t1.y = t.y+p[i].y ;
t2.x = t.x+p[i+].x ;
t2.y = t.y+p[i+].y ;
getlinee(t1,t2) ;
cut() ;
}
}
int main()
{
while(~scanf("%d %lf",&n,&r))
{
for(int i = ; i <= n ; i++)
scanf("%lf %lf",&p[i].x,&p[i].y) ;
p[n+] = p[] ;
solve() ;
int t1 = ,t2 = ;
double maxx = 0.0 ;
for(int i = ; i <= newn ; i++)
{
for(int j = i+ ; j <= newn ; j++)
{
double dis = sqrt((newp[i].x-newp[j].x)*(newp[i].x-newp[j].x)+(newp[i].y-newp[j].y)*(newp[i].y-newp[j].y)) ;
if(dis > maxx)
{
maxx = dis ;
t1 = i ;
t2 = j ;
}
}
}
printf("%.4lf %.4lf %.4lf %.4lf\n",newp[t1].x,newp[t1].y,newp[t2].x,newp[t2].y) ;
}
return ;
}
上一篇:SQL操作大全


下一篇:解决:Android 8.0检测不到当前的activity