Advertisement
a53

Arcpsod

a53
Mar 2nd, 2020
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. // implementare: Cristi Dospra
  2. // punctaj: 100p
  3. // complexitate: O(NlogN)
  4.  
  5. #include <fstream>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <iomanip>
  9. using namespace std;
  10.  
  11. #define NMAX 100002
  12.  
  13. ifstream fin("archpsod.in");
  14. ofstream fout("archpsod.out");
  15.  
  16. struct point {
  17. int x, y;
  18. };
  19.  
  20. point v[NMAX];
  21.  
  22. inline int sqr(int x) {
  23. return x * x;
  24. }
  25.  
  26. inline double dist(point A, point B) {
  27.  
  28. return sqrt(1.0 * (sqr(A.x - B.x) + sqr(A.y - B.y)));
  29. }
  30.  
  31. point Hull[NMAX];
  32.  
  33. inline int det(point A, point B, point C) {
  34.  
  35. return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
  36. }
  37.  
  38. int MakeHull(int N) {
  39.  
  40. int L = 0;
  41.  
  42. for (int i = 1; i <= N; ++i) {
  43. while (L > 1 && det(Hull[L-1], Hull[L], v[i]) <= 0)
  44. L--;
  45. Hull[++L] = v[i];
  46. }
  47.  
  48. int l = L;
  49.  
  50. for (int i = N; i >= 1; --i) {
  51. while (L > l && det(Hull[L-1], Hull[L], v[i]) <= 0)
  52. L--;
  53. Hull[++L] = v[i];
  54. }
  55.  
  56. L--;
  57.  
  58. return L;
  59. }
  60.  
  61. inline bool cmp(point A, point B) {
  62.  
  63. if (A.x == B.x)
  64. return A.y < B.y;
  65.  
  66. return A.x < B.x;
  67. }
  68.  
  69. int main() {
  70.  
  71. int N;
  72. fin >> N;
  73.  
  74. for (int i = 1; i <= N; ++i)
  75. fin >> v[i].x >> v[i].y;
  76.  
  77. sort(v + 1, v + N + 1, cmp);
  78.  
  79. int T = MakeHull(N);
  80.  
  81. double Sol = 0.0;
  82.  
  83. for (int i = 1; i <= T; ++i)
  84. for (int j = i + 1; j <= T; ++j)
  85. Sol = max(Sol, dist(Hull[i], Hull[j]));
  86.  
  87. fout << fixed << setprecision(6) << Sol << "\n";
  88.  
  89. return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement