poj 3384 Feng Shui(半平面交)

发布时间:2017-2-24 9:31:33 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3384 Feng Shui(半平面交)",主要涉及到poj 3384 Feng Shui(半平面交)方面的内容,对于poj 3384 Feng Shui(半平面交)感兴趣的同学可以参考一下。

用两个圆去覆盖多边形,问最多能覆盖多少面积,输出最终两个圆的圆心坐标。 把多边形的各边向内推进r距离,因为题目保证输入合法,则推进后必定能形成一个多边形,只要找这个多边形的距离最远的两个点就行了。 #include<iostream> #include<cstdio> #include<string.h> #include<algorithm> #include<math.h> #include<queue> #include<stack> #include<map> #include<vector> #define mm(a,b) memset(a,b,sizeof(a)) #define maxn 305 using namespace std; const int inf=0x7ffffff; const double PI=acos(-1.0); const double eps=1e-7; const double e=2.7182818284590452354; struct point { double x,y; point() {} point(double x,double y): x(x),y(y) {} }p[maxn],q[maxn],pnt[maxn]; int cnt,curcnt,n; void initial() { for(int i=1;i<=n;i++) p[i]=pnt[i]; p[n+1]=p[1]; p[0]=p[n]; cnt=n; } //两点确定直线 void getline(point x,point y,double &a,double &b,double &c) { a=y.y-x.y; b=x.x-y.x; c=y.x*x.y-x.x*y.y; } //求交点 point intersect(point x,point y,double a,double b,double c) { double u=fabs(a*x.x+b*x.y+c); double v=fabs(a*y.x+b*y.y+c); return point((v*x.x+u*y.x)/(u+v),(v*x.y+u*y.y)/(u+v)); } //直线切割 void cut(double a,double b,double c) { curcnt=0; for(int i=1;i<=cnt;i++) { if(a*p[i].x+b*p[i].y+c>=0)//当前点在直线右侧 q[++curcnt]=p[i]; else { if(a*p[i-1].x+b*p[i-1].y+c>0)//前一个点在直线右侧 q[++curcnt]=intersect(p[i],p[i-1],a,b,c); if(a*p[i+1].x+b*p[i+1].y+c>0)//同理 q[++curcnt]=intersect(p[i],p[i+1],a,b,c); } } for(int i=1;i<=curcnt;i++) p[i]=q[i]; p[curcnt+1]=p[1]; p[0]=p[curcnt]; cnt=curcnt; } void solve(double r) { initial(); //向内推进r for(int i=1;i<=n;i++) { point ta,tb,tt; tt.x=pnt[i+1].y-pnt[i].y; tt.y=pnt[i].x-pnt[i+1].x; double k=r/sqrt(tt.x*tt.x+tt.y*tt.y); tt.x=tt.x*k; tt.y=tt.y*k; 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; double a,b,c; getline(ta,tb,a,b,c); cut(a,b,c); } } double dist(point a,point b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int main() { int t,p1,p2; double r; while(~scanf("%d%lf",&n,&r)) { for(int i=1;i<=n;i++) scanf("%lf%lf",&pnt[i].x,&pnt[i].y); pnt[n+1]=pnt[1]; pnt[0]=pnt[n]; solve(r); double mm=0; p1=p2=1;//开始没有考虑到只有一个点的情况,RE到死。。。 for(int i=1;i<=cnt;i++) for(int j=i+1;j<=cnt;j++) { if(mm<dist(p[i],p[j])) { mm=dist(p[i],p[j]); p1=i; p2=j; } } printf("%.4lf %.4lf %.4lf %.4lf\n",p[p1].x,p[p1].y,p[p2].x,p[p2].y); } return 0; }

上一篇:
下一篇:poj 1665 Biker's Trip Odometer

相关文章

相关评论