daily pastebin goal
52%
SHARE
TWEET

Untitled

a guest May 20th, 2018 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  7. const double eps = 0.0000001;
  8. struct vect
  9. {
  10.     double x, y;
  11. };
  12. struct point
  13. {
  14.     double x,y;
  15. };
  16. struct line
  17. {
  18.     double a,b,c;
  19. };
  20.  
  21. int n;
  22. point a[250];
  23. double BC,AC,AB;
  24. int ans1,ans2,ans3;
  25. vector<pair <int, int > > ansost;
  26. double ans;
  27. point ansp;
  28. double dist(point aa, point b)
  29. {
  30.     return sqrt((aa.x-b.x)*(aa.x-b.x)+(aa.y-b.y)*(aa.y-b.y));
  31. }
  32. vector<pair <double,pair<int,int> > > g;
  33. const int INF = 1000000000;
  34.  
  35. void deyk()
  36. {
  37.     int s = 5;
  38.     vector <pair<int, int> > g1[10];
  39.    
  40.     vector<int> d (n, INF),  p (n);
  41.     d[s] = 0;
  42.     vector<char> u (n);
  43.     for (int i=0; i<n; ++i) {
  44.         int v = -1;
  45.         for (int j=0; j<n; ++j)
  46.             if (!u[j] && (v == -1 || d[j] < d[v]))
  47.                 v = j;
  48.         if (d[v] == INF)
  49.             break;
  50.         else
  51.         u[v] = true;
  52.  
  53.         for (size_t j=0; j<g1[v].size(); ++j) {
  54.             int to = g1[v][j].first,
  55.                 len = g1[v][j].second;
  56.             if (d[v] + len < d[to]) {
  57.                 d[to] = d[v] + len;
  58.                 p[to] = v;
  59.             }
  60.         }
  61.     }
  62. }
  63.  
  64. vector < pair<int,int> >res;
  65. double solve()
  66. {
  67.     double cost=0;
  68.     res.clear();
  69.     sort(g.begin(),g.end());
  70.     vector<int> tree_id(g.size());
  71.     for(int i=0;i<g.size();++i)
  72.     tree_id[i]=i;
  73.     for(int i=0;i<g.size();++i)
  74.     {
  75.         int a1=g[i].second.first,b=g[i].second.second;
  76.         double l=g[i].first;
  77.         if(tree_id[a1]!=tree_id[b])
  78.         {
  79.             cost+=l;
  80.             res.push_back(make_pair(a1,b));
  81.             int old_id=tree_id[b],new_id=tree_id[a1];
  82.             for(int j=0;j<g.size();++j)
  83.                 if(tree_id[j]==old_id)
  84.                     tree_id[j]=new_id;
  85.         }
  86.     }
  87.     return cost;
  88. }
  89. void make_chnge(int h,int h1,int h2,point pp)
  90. {
  91.     g.push_back(make_pair(dist(pp,a[h]),make_pair(n,h)));
  92.     g.push_back(make_pair(dist(pp,a[h1]),make_pair(n,h1)));
  93.     g.push_back(make_pair(dist(pp,a[h2]),make_pair(n,h2)));
  94.     double tmp=solve();
  95.     if(tmp<ans)
  96.     {
  97.         ans=tmp;
  98.         ansp=pp;
  99.         ansost=res;
  100.         ans1=h+1;
  101.         ans2=h1+1;
  102.         ans3=h2+1;
  103.     }
  104. }
  105.  
  106. line make_line(point p1,point p2)
  107. {
  108.     line ans;
  109.     ans.a=p2.y-p1.y;
  110.     ans.b=p1.x-p2.x;
  111.     ans.c=(-(p2.y-p1.y)*p1.x-(p1.x-p2.x)*p1.y);
  112.     return ans;
  113. }
  114. int check_on_line_all_ost(point Ao,point Bo,point Co)
  115. {
  116.     line lineBC=make_line(Bo,Co);
  117.     double ss=lineBC.a*Ao.x+lineBC.b*Ao.y+lineBC.c;
  118.     if(ss<=eps && ss>=-eps)
  119.     {
  120.         return 0;
  121.     }
  122.     return 1;
  123. }
  124. bool check_alf(double A,double B,double C)
  125. {
  126.     return((A*A-B*B-C*C)/(-2*B*C)<-0.5);
  127. }
  128. bool check_ost(int f)
  129. {
  130.     return ansost[f].first!=n && ansost[f].second!=n;
  131. }
  132. point find_point(point a,point b,point c)
  133. {
  134.     vect v1;
  135.     point P1,P2,F1;
  136.     v1.x=b.x-a.x;
  137.     v1.y=b.y-a.y;
  138.     P1.x=(a.x+b.x)/2+v1.y*sqrt(3)/2.0;
  139.     P1.y=(a.y+b.y)/2+(-v1.x*sqrt(3)/2.0);
  140.     P2.x=(a.x+b.x)/2-v1.y * sqrt(3)/2.0;
  141.     P2.y=(a.y+b.y)/2-(-v1.x*sqrt(3)/2.0);
  142.     if(dist(P1,c)>dist(P2,c))
  143.         F1=P1;
  144.     else
  145.         F1=P2;
  146.     return F1;
  147. }
  148.  
  149. point Ferma(point A,point B,point C)
  150. {
  151.    
  152.     BC=dist(B,C);
  153.     AC=dist(A,C);
  154.     AB=dist(A,B);
  155.     if(!check_on_line_all_ost(A,B,C))
  156.     {
  157.         point gg;
  158.         gg.x=-10000;
  159.         gg.y=-10000;
  160.         return gg;
  161.     }
  162.     if(check_alf(BC,AC,AB))
  163.     {
  164.         point gg;
  165.         gg.x=-10000;
  166.         gg.y=-10000;
  167.         return gg;
  168.     }
  169.     if(check_alf(AC,BC,AB))
  170.     {
  171.         point gg;
  172.         gg.x=-10000;
  173.         gg.y=-10000;
  174.         return gg;
  175.     }
  176.     if(check_alf(AB,AC,BC))
  177.     {
  178.         point gg;
  179.         gg.x=-10000;
  180.         gg.y=-10000;
  181.         return gg;
  182.     }
  183.     point P1=find_point(A,B,C);
  184.     point P2=find_point(A,C,B);
  185.     line L1=make_line(C,P1);
  186.     line L2=make_line(B,P2);
  187.     point Pans;
  188.     Pans.x=(L2.b*L1.c-L1.b*L2.c)/(L2.a*L1.b-L1.a*L2.b);
  189.     Pans.y=(L1.b!=0?(-L1.c-L1.a*Pans.x)/L1.b:(-L2.c-L2.a*Pans.x)/L2.b);
  190.     //double ansdist=0;
  191.     /*for(int i=0;i<n;i++)
  192.         ansdist+=dist(Pans,a[i]);
  193.     printf("%.7lf",ansdist);
  194.     cout<<endl;
  195.     printf("%.7lf %.7lf",Pans.x,Pans.y);
  196.     cout<<endl;
  197.     cout<<"3 ";
  198.     cout<<"1 2 3";
  199.     cout<<endl;
  200.     cout<<"0";*/
  201.     //ansdist+=dist(Pans,A)+dist(Pans,B)+dist(Pans,C);
  202.     return Pans;
  203.  
  204. }
  205. int check_on_line_all()
  206. {
  207.     line lineBC=make_line(a[1],a[2]);
  208.     double ss=lineBC.a*a[0].x+lineBC.b*a[0].y+lineBC.c;
  209.     if(ss<=eps && ss>=-eps)
  210.     {
  211.         double ans;
  212.         ans=max(AB, max(AC,BC));
  213.         printf("%.6lf\n", ans);
  214.         cout<<"0 0";
  215.         cout<<endl;
  216.         cout<<"0";
  217.         cout<<endl;
  218.         cout<<"2";
  219.         cout<<endl;
  220.         if(ans==AB)
  221.         {
  222.             cout<<"1 ";
  223.             cout<<"3";
  224.             cout<<endl;
  225.             cout<<"2 ";
  226.             cout<<"3";
  227.             cout<<endl;
  228.         }
  229.         if(ans==AC)
  230.         {
  231.             cout<<"1 ";
  232.             cout<<"2";
  233.             cout<<endl;
  234.             cout<<"2 ";
  235.             cout<<"3";
  236.             cout<<endl;
  237.         }
  238.         if(ans==BC)
  239.         {
  240.             cout<<"1 ";
  241.             cout<<"2";
  242.             cout<<endl;
  243.             cout<<"1 ";
  244.             cout<<"3";
  245.             cout<<endl;
  246.         }
  247.         return 0;
  248.     }
  249.     return 1;
  250. }
  251.  
  252.  
  253. int main()
  254. {
  255.     cin>>n;
  256.     if(n==1)
  257.     {
  258.         cout<<"0";
  259.         cout<<endl;
  260.         cout<<"0 ";
  261.         cout<<"0";
  262.         cout<<endl;
  263.         cout<<"0";
  264.         cout<<endl;
  265.         cout<<"0";
  266.         return 0;
  267.     }
  268.     if (n == 2)
  269.     {
  270.         point a1[2];
  271.         cin>>a1[0].x>>a1[0].y>>a1[1].x>>a1[1].y;
  272.         printf("%.7lf\n",dist(a1[0],a1[1]));
  273.         cout<<"0 ";
  274.         cout<<"0";
  275.         cout<<endl;
  276.         cout<<"0";
  277.         cout<<endl;
  278.         cout<<"1";
  279.         cout<<endl;
  280.         cout<<"1 ";
  281.         cout<<"2";
  282.         return 0;
  283.     }
  284.    
  285.     for(int i=0;i<n;i++)
  286.         cin>>a[i].x>>a[i].y;
  287.     g.clear();
  288.     for(int i=0;i<n;i++)
  289.         for(int j=0;j<n;j++)
  290.             g.push_back(make_pair(dist(a[i],a[j]),make_pair(i,j)));
  291.         ans=solve();
  292.         //point ansp;
  293.         ansp.x=-10000;
  294.        
  295.         ansost=res;
  296.         for(int i=0;i<n;i++)
  297.             for(int j=0;j<n;j++)
  298.                 for(int k=0;k<n;k++)
  299.                     if(i!=j && i!=k && j!=k)
  300.                     {
  301.                         point fer=Ferma(a[i],a[j],a[k]);
  302.                         if(fer.x!=-10000)
  303.                         {
  304.                             make_chnge(i,j,k,fer);
  305.                             g.clear();
  306.                             for(int i1=0;i1<n;i1++)
  307.                                 for(int j1=0;j1<n;j1++)
  308.                                     g.push_back(make_pair(dist(a[i1],a[j1]),make_pair(i1,j1)));
  309.                         }
  310.                     }
  311.         printf("%.7lf",ans);
  312.         cout<<endl;
  313.         if(ansp.x==-10000)
  314.         {
  315.             cout<<0<<" ";
  316.             cout<<0;
  317.             cout<<endl;
  318.             cout<<0;
  319.             cout<<endl;
  320.         }
  321.         else
  322.         {
  323.             printf("%.7lf %.7lf",ansp.x,ansp.y);
  324.             cout<<endl;
  325.             cout<<"3 ";
  326.             cout<<ans1;
  327.             cout<<" ";
  328.             cout<<ans2;
  329.             cout<<" ";
  330.             cout<<ans3;
  331.             //printf("%d %d %d",ans1,ans2,ans3);
  332.             cout<<endl;
  333.         }
  334.         int perem=0;
  335.         int sz_ostov=ansost.size();
  336.         for(int i=0;i<sz_ostov;i++)
  337.         {
  338.             if(check_ost(i))
  339.                 perem++;
  340.         }
  341.         cout<<perem<<endl;
  342.         for(int i=0;i<sz_ostov;i++)
  343.         {
  344.             if(check_ost(i))
  345.                 cout<<ansost[i].first+1<<" "<<ansost[i].second+1<<endl;
  346.         }
  347.                
  348.     return 0;
  349. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top