• API
• FAQ
• Tools
• Archive
daily pastebin goal
22%
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.

Top