【计算几何】【预处理】【枚举】Urozero Autumn Training Camp 2016 Day 5: NWERC-2016 Problem K. Kiwi Trees
2024-10-21 03:55:58
发现由于角的度数和边的长度有限制,那俩圆如果放得下的话,必然是塞在两个角里。
于是预处理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;
}
最新文章
- C#操作SQLite数据库
- __autoload的小tip
- 认识IoC
- 点击不同按钮生成不同窗体到某个panel上面,类似Frame用法--不错
- 使用即时文件初始化提高SQL Server性能
- maven出错The folder is already a source folder
- @Autowired失效
- 基于WebForm+EasyUI的业务管理系统形成之旅 -- 构建Web界面(Ⅴ)
- 保留脚本中变量(dot)
- form表单提交
- php使用PDO方法详解
- web.py入门
- java利用WatchService实时监控某个目录下的文件变化并按行解析(注:附源代码)
- Java线程和守护进程
- NOIP2014-3-15模拟赛
- markdown箭头的处理
- JAVA主流框架---SSM整合
- zabbix 常用监控模板
- android构建过程
- nginx安装lua模块实现高并发