首页 > 代码库 > POJ 3384 Feng Shui(半平面交向内推进求最远点对)
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[110],temp[110],newp[110]; 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 = 0 ; for(int i = 1 ; i <= newn ; i++) { if(newp[i].x*a+newp[i].y*b+c >= 0) temp[++cutn] = newp[i] ; else { if(newp[i-1].x*a+newp[i-1].y*b+c > 0) temp[++cutn] = intersect(newp[i-1],newp[i]) ; if(newp[i+1].x*a+newp[i+1].y*b+c > 0) temp[++cutn] = intersect(newp[i+1],newp[i]) ; } } for(int i = 1 ; i <= cutn ; i++) newp[i] = temp[i] ; newp[cutn+1] = newp[1] ; newp[0] = newp[cutn] ; newn = cutn ; //printf("newn%d = %d\n",cnt++,newn) ; } void solve() { for(int i = 1 ; i <= n ; i ++) { newp[i] = p[i] ; } newp[n+1] = p[1] ; newp[0] = p[n] ; newn = n ; for(int i = 1 ; i <= n ; i++) { node t,t1,t2 ; t.x = p[i+1].y-p[i].y ; t.y = p[i].x-p[i+1].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+1].x ; t2.y = t.y+p[i+1].y ; getlinee(t1,t2) ; cut() ; } } int main() { while(~scanf("%d %lf",&n,&r)) { for(int i = 1 ; i <= n ; i++) scanf("%lf %lf",&p[i].x,&p[i].y) ; p[n+1] = p[1] ; solve() ; int t1 = 0,t2 = 0 ; double maxx = 0.0 ; for(int i = 1 ; i <= newn ; i++) { for(int j = i+1 ; 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 0 ; }
POJ 3384 Feng Shui(半平面交向内推进求最远点对)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。