fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <math.h>
  4. #include <cmath>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <iterator>
  9. #include <vector>
  10. #include <stdio.h>
  11. #include <queue>
  12. #include <deque>
  13. #include <stack>
  14. using namespace std;
  15. typedef long ll;
  16. typedef unsigned long long ull;
  17. typedef double ld;
  18. ll i, j, n;
  19. ld ax, ay, bx, byy, tx, ty, all=0.0,  sum=0.0;
  20. struct rasp
  21. {
  22. 	ld x;
  23. 	ld y;
  24. 	ld d;
  25. };
  26. rasp r[100005];
  27. ld ar[100005], br[100005], ad[100005], bd[100005];
  28. set < pair < ld, ll > >  aa, bb;
  29. set < pair < ld, ll > >::iterator q,it,ti;
  30. ld sum_now;
  31. int main()
  32. {
  33. 	cin >> ax >> ay >> bx >> byy >> tx >> ty;
  34. 	cin >> n;
  35. 	for (i = 0; i < n; i++)
  36. 	{
  37. 		cin >> r[i].x >> r[i].y;
  38. 		r[i].d = sqrt((r[i].x - tx)*(r[i].x - tx) + (r[i].y - ty)*(r[i].y - ty));
  39. 		all += r[i].d * 2;
  40. 		ld di= sqrt((r[i].x - ax)*(r[i].x - ax) + (r[i].y - ay)*(r[i].y - ay));
  41. 		ar[i] = di-r[i].d;
  42. 		ad[i] = di;
  43. 		aa.insert(make_pair(di-r[i].d, i));
  44. 		di = sqrt((r[i].x - bx)*(r[i].x - bx) + (r[i].y - byy)*(r[i].y - byy));
  45. 		bb.insert(make_pair(di - r[i].d , i));
  46. 		br[i] = di-r[i].d;
  47. 		bd[i] = di;
  48. 	}
  49.     q=aa.begin();
  50. 	ld suma = all + ar[q->second];
  51. 	q = bb.begin();
  52. 	ld sumb = all + br[q->second];
  53. 	if(suma>sumb)
  54.         sum = sumb;
  55. 	else
  56.         sum=suma;
  57. 	if (n > 1)
  58. 	{
  59. 		for (it = aa.begin(); it != aa.end(); it++)
  60. 		{
  61. 			i = it->second;
  62. 			bb.erase(bb.find(make_pair(br[i], i)));
  63. 			ti = bb.begin();
  64. 			j = ti->second;
  65. 			sum_now = all + ar[i] + br[j];
  66. 			if(sum>sum_now)
  67.                 sum=sum_now;
  68. 			bb.insert(make_pair(br[i], i));
  69. 		}
  70. 	}
  71. 	printf("%.7f", sum);
  72. }
  73.  
Success #stdin #stdout 0s 8888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000
https://ideone.com/bjt3KI
language:
C++14 (gcc 8.3)
created:
8 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!