读懂题意其实是模板题。就是细节略多。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define EPS 0.00000001
struct Point
{
double x,y;
Point(){}
Point(const double &X,const double &Y){x=X;y=Y;}
double Length()
{
return sqrt(x*x+y*y);
}
}p[3],a[31];
struct data
{
Point p;
int I,J;
data(){}
data(const Point &P,const int &II,const int &JJ)
{
p=P;
I=II;
J=JJ;
}
}b[31];
int e;
typedef Point Vector;
Vector operator - (const Point &a,const Point &b)
{
return Vector(a.x-b.x,a.y-b.y);
}
Vector operator + (const Vector &a,const Vector &b)
{
return Vector(a.x+b.x,a.y+b.y);
}
double Cross(Vector a,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);
}
Point GetIntersection(Point P,Vector v,Point Q,Vector w)
{
return P+(Cross(w,P-Q)/Cross(v,w))*v;
}
double dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
bool InLine(Point a,Point P,Point Q)
{
if(fabs(Cross(a-P,Q-P))>=EPS)
return 0;
return dot(a-P,a-Q)<EPS;
}
int n;
int main()
{
// freopen("s.in","r",stdin);
double sum=0;
for(int i=0;i<2;++i)
scanf("%lf%lf",&p[i].x,&p[i].y);
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=0;i<n;++i)
if(fabs(Cross(p[1]-a[(i+1)%n],a[i]-p[0]))<EPS)
{
printf("%.9lf\n",(p[1]-p[0]).Length());
return 0;
}
for(int i=0;i<n;++i)
sum+=(a[(i+1)%n]-a[i]).Length();
/*double sum2=0;
for(int k=i+1;k<j;++k)
sum2+=(a[(k+1)%n]-a[k]).Length();
sum2+=(a[i+1]-tp).Length();
sum2+=(tp2-a[j]).Length();
double td=min((tp-p[0]).Length()+(tp2-p[1]).Length(),
(tp2-p[0]).Length()+(tp-p[1]).Length());
printf("%.9lf\n",td+min(sum-sum2,min(sum2,(tp2-tp).Length()*2.0)));*/
for(int i=0;i<n;++i)
{
Point tp=GetIntersection(p[1],p[1]-p[0],a[i],a[(i+1)%n]-a[i]);
if(InLine(tp,a[i],a[(i+1)%n]) && InLine(tp,p[0],p[1]))
{
for(int j=i+1;j<n;++j)
{
Point tp2=GetIntersection(p[1],p[1]-p[0],a[j],a[(j+1)%n]-a[j]);
if(InLine(tp2,a[j],a[(j+1)%n]) && InLine(tp2,p[0],p[1]))
b[++e]=data(tp2,i,j);
}
for(int j=1;j<=e;++j)
if(fabs(b[j].p.x-tp.x)>=EPS || fabs(b[j].p.y-tp.y)>=EPS)
{
int I=b[j].I,J=b[j].J;
Point tp2=b[j].p;
double sum2=0;
for(int k=I+1;k<J;++k)
sum2+=(a[(k+1)%n]-a[k]).Length();
sum2+=(a[I+1]-tp).Length();
sum2+=(tp2-a[J]).Length();
double td=min((tp-p[0]).Length()+(tp2-p[1]).Length(),
(tp2-p[0]).Length()+(tp-p[1]).Length());
printf("%.9lf\n",td+min(sum-sum2,min(sum2,(tp2-tp).Length()*2.0)));
return 0;
}
int I=b[1].I,J=b[1].J;
Point tp2=b[1].p;
double sum2=0;
for(int k=I+1;k<J;++k)
sum2+=(a[(k+1)%n]-a[k]).Length();
sum2+=(a[I+1]-tp).Length();
sum2+=(tp2-a[J]).Length();
double td=min((tp-p[0]).Length()+(tp2-p[1]).Length(),
(tp2-p[0]).Length()+(tp-p[1]).Length());
printf("%.9lf\n",td+min(sum-sum2,min(sum2,(tp2-tp).Length()*2.0)));
return 0;
}
}
printf("%.9lf\n",(p[1]-p[0]).Length());
return 0;
}

最新文章

  1. 练习1-12:编写一个程序,以每行一个单词的形式打印其输入(C程序设计语言 第2版)
  2. 深入理解Ember-Data特性(下)
  3. Daily Scrum 10.25
  4. velocity 判断 变量 是否不是空或empty
  5. PowerDesigner(三)-企业架构模型(转)
  6. MySQL参数调优最佳实践
  7. Solr配置集群
  8. 数组对象元素的添加,String对象,BOM对象以及文档对象的获取
  9. 实现Web虚拟现实的最轻松方案—A-Frame框架
  10. 开源项目之Android Afinal框架
  11. 【转】关于C语言生成不重复的随机数
  12. C,C++中的static
  13. [妙味 DOM] 第二课:DOM、BOM相关方法及属性
  14. python 操作PostgreSQL
  15. JS Arry 常用方法总结
  16. 派多个订单给一个司机,拒单是同一订单id
  17. jmeter学习记录--03--jmeter负载与监听
  18. 使用Git进行协同开发
  19. qt——QObject 与 QWidget 的区别
  20. UVA - 11920 0 s, 1 s and ? Marks

热门文章

  1. [SDOI2011]消防/[NOIP2007] 树网的核
  2. json解析之jackson
  3. Java多线程-一个简单的线程,实现挂起和恢复的功能
  4. JS模块化工具requirejs教程02
  5. nginx的常规配置
  6. 图论:Gale-Shapley算法
  7. 【hdu2825-Wireless Password】AC自动机+DP
  8. 基于x64的处理器意思
  9. 使用maven构建第一个web项目
  10. Winform常用操作