fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll MOD = 1e9+7;
  6. const double INF = 1e18;
  7. const int N = 505;
  8.  
  9.  
  10. struct Point{
  11.     ll x,y;
  12.     Point(ll _x=0,ll _y=0){
  13.         x=_x;
  14.         y=_y;
  15.     }
  16. }p[N];
  17.  
  18. int ori(Point p1,Point p2,Point p3){
  19.     ll val=(p2.y-p1.y)*(p3.x-p2.x)-(p2.x-p1.x)*(p3.y-p2.y);
  20.  
  21.     if(val>0)return 1;
  22.     return 2;
  23. }
  24.  
  25. bool intersect(Point p1,Point q1,Point p2,Point q2){
  26.     int o1=ori(p1,q1,p2);
  27.     int o2=ori(p1,q1,q2);
  28.     int o3=ori(p2,q2,p1);
  29.     int o4=ori(p2,q2,q1);
  30.  
  31.     if(o1!=o2&&o3!=o4)return true;
  32.     return false;
  33. }
  34.  
  35. double dist(Point p1,Point p2){
  36.     ll dx=abs(p1.x-p2.x);
  37.     ll dy=abs(p1.y-p2.y);
  38.  
  39.     return sqrt((double)dx*dx+(double)dy*dy);
  40. }
  41.  
  42. int quad(Point p1){
  43.     if(p1.x<=0&&p1.y>=0)return 1;
  44.     if(p1.x>0&&p1.y>0)return 2;
  45.     if(p1.x>0&&p1.y<=0)return 3;
  46.     return 4;
  47. }
  48.  
  49. bool cmp(const Point &p1,const Point &p2){
  50.     if(quad(p1)!=quad(p2))return quad(p1)<quad(p2);
  51.     int o=ori(Point(),p1,p2);
  52.     if(o==1)return true;
  53.     return false;
  54. }
  55.  
  56. int n;
  57. double dp[N][N];
  58. bool ok[N][N];
  59.  
  60. double solve(int from,int to){
  61.     if(from>to)return 0.0;
  62.     if(dp[from][to]!=INF)return dp[from][to];
  63.  
  64.     int c=0;
  65.     for(int i=from+1;i<to;i++){
  66.         if(!c&&ok[from][i])dp[from][to]=min(dp[from][to],dist(Point(),p[from])+dist(p[from],p[i])+dist(p[i],Point())+solve(from+1,i-1)+solve(i+1,to));
  67.         c^=1;
  68.     }
  69.  
  70.     if(ok[from][to])dp[from][to]=min(dp[from][to],solve(from+1,to-1)+dist(Point(),p[from])+dist(Point(),p[to])+dist(p[from],p[to]));
  71.  
  72.     return dp[from][to];
  73. }
  74.  
  75.  
  76. int main()
  77. {
  78.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  79.     cin>>n;
  80.     for(int i=1;i<=n;i++){
  81.         cin>>p[i].x>>p[i].y;
  82.     }
  83.  
  84.     sort(p+1,p+1+n,cmp);
  85.  
  86.     for(int i=1;i<=n;i++){
  87.         for(int j=1;j<=n;j++){
  88.             if(i==j)continue;
  89.             ok[i][j]=true;
  90.             for(int k=1;k<=n;k++){
  91.                 if(i!=k&&j!=k){
  92.                     if(intersect(p[i],p[j],p[k],Point()))ok[i][j]=false;
  93.                 }
  94.             }
  95.         }
  96.     }
  97.  
  98.     for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=INF;
  99.  
  100.     cout<<fixed<<setprecision(6)<<solve(1,n);
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 17488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000000
https://ideone.com/w0O08P
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!