Advertisement
999ms

Untitled

Jan 31st, 2020
451
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. int main() {
  8.     ios_base::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.     cout.tie(nullptr);
  11.     int n;
  12.     cin >> n;
  13.     vector<int> x(n), y(n);
  14.     for (int i = 0; i < n; i++) {
  15.         cin >> x[i] >> y[i];
  16.     }
  17.     vector<pair<ll, pair<int,int>>> lines;
  18.     for (int i = 0; i < n; i++) {
  19.         for (int j = 0; j < i; j++) {
  20.             lines.push_back({(x[i] - x[j]) * 1ll * (x[i] - x[j]) + (y[i] - y[j]) * 1ll * (y[i] - y[j]), {i, j}});
  21.         }
  22.     }
  23.     sort(all(lines), greater<>());
  24.     auto cw = [&] (int x1, int y1, int x2, int y2) {
  25.         return 1ll * x1 * y2 == 1ll * x2 * y1;
  26.     };
  27.     double answer = 0;
  28.     vector<vector<int>> used(n);
  29.     for (auto& [len, p] : lines) {
  30.         auto& [i, j] = p;
  31.         bool good = true;
  32.         for (int v : used[i]) {
  33.             if (cw(x[i] - x[j], y[i] - y[j], x[i] - x[v], y[i] - y[v])) {
  34.                 good = false;
  35.             }
  36.         }
  37.        
  38.         for (int v : used[j]) {
  39.             if (cw(x[i] - x[j], y[i] - y[j], x[j] - x[v], y[j] - y[v])) {
  40.                 good = false;
  41.             }
  42.         }
  43.        
  44.         if (good) {
  45.             answer += sqrt(len);
  46.         }
  47.        
  48.         used[i].push_back(j);
  49.         used[j].push_back(i);
  50.     }
  51.     cout << fixed << setprecision(0) << answer << endl;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement