首页 > 代码库 > 【计算几何】【预处理】【枚举】Urozero Autumn Training Camp 2016 Day 5: NWERC-2016 Problem K. Kiwi Trees
【计算几何】【预处理】【枚举】Urozero Autumn Training Camp 2016 Day 5: NWERC-2016 Problem K. Kiwi Trees
发现由于角的度数和边的长度有限制,那俩圆如果放得下的话,必然是塞在两个角里。
于是预处理n个圆心的位置(注意要判断那个圆会不会和其他的边界相交),然后n^2枚举俩角即可。
#include<cstdio> #include<cmath> using namespace std; #define EPS 0.00000001 struct Point{ double x,y; double length(){ return sqrt(x*x+y*y); } }a[2010]; typedef Point Vector; Vector unit(Vector v){ double l=v.length(); return (Vector){v.x/l,v.y/l}; } Vector operator - (const Point &a,const Point &b){ return (Vector){a.x-b.x,a.y-b.y}; } Vector operator + (const Point &a,const Point &b){ return (Vector){a.x+b.x,a.y+b.y}; } double dot(const Vector &a,const Vector &b){ return a.x*b.x+a.y*b.y; } double Cross(const Vector &a,const Vector &b){ return a.x*b.y-a.y*b.x; } Vector operator * (const double &K,const Vector &v){ return (Vector){K*v.x,K*v.y}; } int n; Point calc(int I){ double jiao=acos(dot(a[I+1]-a[I],a[I-1]-a[I])/(a[I+1]-a[I]).length()/(a[I-1]-a[I]).length()); double d=4000.0/tan(jiao/2.0); double l=4000.0/sin(jiao/2.0); Point p1=a[I]+d*unit(a[I+1]-a[I]); Point p2=a[I]+d*unit(a[I-1]-a[I]); Point M=(Point){(p1.x+p2.x)/2.0,(p1.y+p2.y)/2.0}; return a[I]+l*unit(M-a[I]); } double DisToSegment(Point P,Point A,Point B) { Vector v1=B-A,v2=P-A,v3=P-B; if(dot(v1,v2)<EPS) return v2.length(); else if(dot(v1,v3)>EPS) return v3.length(); else return fabs(Cross(v1,v2))/v1.length(); } Point yuanxins[2010]; bool can[2010]; int main(){ // freopen("k.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%lf%lf",&a[i].x,&a[i].y); } a[++n]=a[1]; for(int i=n;i>=1;--i){ a[i+1]=a[i]; } a[1]=a[n]; ++n; for(int i=2;i<n;++i){ yuanxins[i]=calc(i); can[i]=1; for(int j=2;j<n;++j){ // double tmp=DisToSegment(yuanxins[i],a[j],a[j+1]); if(DisToSegment(yuanxins[i],a[j],a[j+1])-4000.0<-EPS){ can[i]=0; break; } } } for(int i=2;i<n;++i){ if(Cross(a[i+1]-a[i],a[i]-a[i-1])>EPS && can[i]){ Point A=yuanxins[i]; for(int j=i+1;j<n;++j){ if(Cross(a[j+1]-a[j],a[j]-a[j-1])>EPS && can[j]){ Point B=yuanxins[j]; // double tmp=(B-A).length(); if((B-A).length()-8000.0>-EPS){ printf("%.8f %.8f\n%.8f %.8f\n",A.x,A.y,B.x,B.y); return 0; } } } } } puts("impossible"); return 0; }
【计算几何】【预处理】【枚举】Urozero Autumn Training Camp 2016 Day 5: NWERC-2016 Problem K. Kiwi Trees
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。