Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const double eps = 0.0000001;
- struct vect
- {
- double x, y;
- };
- struct point
- {
- double x,y;
- };
- struct line
- {
- double a,b,c;
- };
- int n;
- point a[250];
- double BC,AC,AB;
- int ans1,ans2,ans3;
- vector<pair <int, int > > ansost;
- double ans;
- point ansp;
- double dist(point aa, point b)
- {
- return sqrt((aa.x-b.x)*(aa.x-b.x)+(aa.y-b.y)*(aa.y-b.y));
- }
- vector<pair <double,pair<int,int> > > g;
- const int INF = 1000000000;
- void deyk()
- {
- int s = 5;
- vector <pair<int, int> > g1[10];
- vector<int> d (n, INF), p (n);
- d[s] = 0;
- vector<char> u (n);
- for (int i=0; i<n; ++i) {
- int v = -1;
- for (int j=0; j<n; ++j)
- if (!u[j] && (v == -1 || d[j] < d[v]))
- v = j;
- if (d[v] == INF)
- break;
- else
- u[v] = true;
- for (size_t j=0; j<g1[v].size(); ++j) {
- int to = g1[v][j].first,
- len = g1[v][j].second;
- if (d[v] + len < d[to]) {
- d[to] = d[v] + len;
- p[to] = v;
- }
- }
- }
- }
- vector < pair<int,int> >res;
- double solve()
- {
- double cost=0;
- res.clear();
- sort(g.begin(),g.end());
- vector<int> tree_id(g.size());
- for(int i=0;i<g.size();++i)
- tree_id[i]=i;
- for(int i=0;i<g.size();++i)
- {
- int a1=g[i].second.first,b=g[i].second.second;
- double l=g[i].first;
- if(tree_id[a1]!=tree_id[b])
- {
- cost+=l;
- res.push_back(make_pair(a1,b));
- int old_id=tree_id[b],new_id=tree_id[a1];
- for(int j=0;j<g.size();++j)
- if(tree_id[j]==old_id)
- tree_id[j]=new_id;
- }
- }
- return cost;
- }
- void make_chnge(int h,int h1,int h2,point pp)
- {
- g.push_back(make_pair(dist(pp,a[h]),make_pair(n,h)));
- g.push_back(make_pair(dist(pp,a[h1]),make_pair(n,h1)));
- g.push_back(make_pair(dist(pp,a[h2]),make_pair(n,h2)));
- double tmp=solve();
- if(tmp<ans)
- {
- ans=tmp;
- ansp=pp;
- ansost=res;
- ans1=h+1;
- ans2=h1+1;
- ans3=h2+1;
- }
- }
- line make_line(point p1,point p2)
- {
- line ans;
- ans.a=p2.y-p1.y;
- ans.b=p1.x-p2.x;
- ans.c=(-(p2.y-p1.y)*p1.x-(p1.x-p2.x)*p1.y);
- return ans;
- }
- int check_on_line_all_ost(point Ao,point Bo,point Co)
- {
- line lineBC=make_line(Bo,Co);
- double ss=lineBC.a*Ao.x+lineBC.b*Ao.y+lineBC.c;
- if(ss<=eps && ss>=-eps)
- {
- return 0;
- }
- return 1;
- }
- bool check_alf(double A,double B,double C)
- {
- return((A*A-B*B-C*C)/(-2*B*C)<-0.5);
- }
- bool check_ost(int f)
- {
- return ansost[f].first!=n && ansost[f].second!=n;
- }
- point find_point(point a,point b,point c)
- {
- vect v1;
- point P1,P2,F1;
- v1.x=b.x-a.x;
- v1.y=b.y-a.y;
- P1.x=(a.x+b.x)/2+v1.y*sqrt(3)/2.0;
- P1.y=(a.y+b.y)/2+(-v1.x*sqrt(3)/2.0);
- P2.x=(a.x+b.x)/2-v1.y * sqrt(3)/2.0;
- P2.y=(a.y+b.y)/2-(-v1.x*sqrt(3)/2.0);
- if(dist(P1,c)>dist(P2,c))
- F1=P1;
- else
- F1=P2;
- return F1;
- }
- point Ferma(point A,point B,point C)
- {
- BC=dist(B,C);
- AC=dist(A,C);
- AB=dist(A,B);
- if(!check_on_line_all_ost(A,B,C))
- {
- point gg;
- gg.x=-10000;
- gg.y=-10000;
- return gg;
- }
- if(check_alf(BC,AC,AB))
- {
- point gg;
- gg.x=-10000;
- gg.y=-10000;
- return gg;
- }
- if(check_alf(AC,BC,AB))
- {
- point gg;
- gg.x=-10000;
- gg.y=-10000;
- return gg;
- }
- if(check_alf(AB,AC,BC))
- {
- point gg;
- gg.x=-10000;
- gg.y=-10000;
- return gg;
- }
- point P1=find_point(A,B,C);
- point P2=find_point(A,C,B);
- line L1=make_line(C,P1);
- line L2=make_line(B,P2);
- point Pans;
- Pans.x=(L2.b*L1.c-L1.b*L2.c)/(L2.a*L1.b-L1.a*L2.b);
- Pans.y=(L1.b!=0?(-L1.c-L1.a*Pans.x)/L1.b:(-L2.c-L2.a*Pans.x)/L2.b);
- //double ansdist=0;
- /*for(int i=0;i<n;i++)
- ansdist+=dist(Pans,a[i]);
- printf("%.7lf",ansdist);
- cout<<endl;
- printf("%.7lf %.7lf",Pans.x,Pans.y);
- cout<<endl;
- cout<<"3 ";
- cout<<"1 2 3";
- cout<<endl;
- cout<<"0";*/
- //ansdist+=dist(Pans,A)+dist(Pans,B)+dist(Pans,C);
- return Pans;
- }
- int check_on_line_all()
- {
- line lineBC=make_line(a[1],a[2]);
- double ss=lineBC.a*a[0].x+lineBC.b*a[0].y+lineBC.c;
- if(ss<=eps && ss>=-eps)
- {
- double ans;
- ans=max(AB, max(AC,BC));
- printf("%.6lf\n", ans);
- cout<<"0 0";
- cout<<endl;
- cout<<"0";
- cout<<endl;
- cout<<"2";
- cout<<endl;
- if(ans==AB)
- {
- cout<<"1 ";
- cout<<"3";
- cout<<endl;
- cout<<"2 ";
- cout<<"3";
- cout<<endl;
- }
- if(ans==AC)
- {
- cout<<"1 ";
- cout<<"2";
- cout<<endl;
- cout<<"2 ";
- cout<<"3";
- cout<<endl;
- }
- if(ans==BC)
- {
- cout<<"1 ";
- cout<<"2";
- cout<<endl;
- cout<<"1 ";
- cout<<"3";
- cout<<endl;
- }
- return 0;
- }
- return 1;
- }
- int main()
- {
- cin>>n;
- if(n==1)
- {
- cout<<"0";
- cout<<endl;
- cout<<"0 ";
- cout<<"0";
- cout<<endl;
- cout<<"0";
- cout<<endl;
- cout<<"0";
- return 0;
- }
- if (n == 2)
- {
- point a1[2];
- cin>>a1[0].x>>a1[0].y>>a1[1].x>>a1[1].y;
- printf("%.7lf\n",dist(a1[0],a1[1]));
- cout<<"0 ";
- cout<<"0";
- cout<<endl;
- cout<<"0";
- cout<<endl;
- cout<<"1";
- cout<<endl;
- cout<<"1 ";
- cout<<"2";
- return 0;
- }
- for(int i=0;i<n;i++)
- cin>>a[i].x>>a[i].y;
- g.clear();
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- g.push_back(make_pair(dist(a[i],a[j]),make_pair(i,j)));
- ans=solve();
- //point ansp;
- ansp.x=-10000;
- ansost=res;
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- for(int k=0;k<n;k++)
- if(i!=j && i!=k && j!=k)
- {
- point fer=Ferma(a[i],a[j],a[k]);
- if(fer.x!=-10000)
- {
- make_chnge(i,j,k,fer);
- g.clear();
- for(int i1=0;i1<n;i1++)
- for(int j1=0;j1<n;j1++)
- g.push_back(make_pair(dist(a[i1],a[j1]),make_pair(i1,j1)));
- }
- }
- printf("%.7lf",ans);
- cout<<endl;
- if(ansp.x==-10000)
- {
- cout<<0<<" ";
- cout<<0;
- cout<<endl;
- cout<<0;
- cout<<endl;
- }
- else
- {
- printf("%.7lf %.7lf",ansp.x,ansp.y);
- cout<<endl;
- cout<<"3 ";
- cout<<ans1;
- cout<<" ";
- cout<<ans2;
- cout<<" ";
- cout<<ans3;
- //printf("%d %d %d",ans1,ans2,ans3);
- cout<<endl;
- }
- int perem=0;
- int sz_ostov=ansost.size();
- for(int i=0;i<sz_ostov;i++)
- {
- if(check_ost(i))
- perem++;
- }
- cout<<perem<<endl;
- for(int i=0;i<sz_ostov;i++)
- {
- if(check_ost(i))
- cout<<ansost[i].first+1<<" "<<ansost[i].second+1<<endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment