发现由于角的度数和边的长度有限制,那俩圆如果放得下的话,必然是塞在两个角里。

于是预处理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;
}

最新文章

  1. C#操作SQLite数据库
  2. __autoload的小tip
  3. 认识IoC
  4. 点击不同按钮生成不同窗体到某个panel上面,类似Frame用法--不错
  5. 使用即时文件初始化提高SQL Server性能
  6. maven出错The folder is already a source folder
  7. @Autowired失效
  8. 基于WebForm+EasyUI的业务管理系统形成之旅 -- 构建Web界面(Ⅴ)
  9. 保留脚本中变量(dot)
  10. form表单提交
  11. php使用PDO方法详解
  12. web.py入门
  13. java利用WatchService实时监控某个目录下的文件变化并按行解析(注:附源代码)
  14. Java线程和守护进程
  15. NOIP2014-3-15模拟赛
  16. markdown箭头的处理
  17. JAVA主流框架---SSM整合
  18. zabbix 常用监控模板
  19. android构建过程
  20. nginx安装lua模块实现高并发

热门文章

  1. 20151024_003_C#基础知识(File / FileStream / StreamReader/StreamWriter)
  2. poj 1797
  3. 理解js中私有变量
  4. PHP序列化、反序列化常用的魔术方法
  5. Java 关于微信公众号支付总结附代码
  6. php快速入门总结
  7. AJAX 核心 —— XMLHTTPRequest 对象回顾
  8. python基础===继承
  9. C基础入门 - 第一章 - C语言绪言
  10. php 读写 csv文件