fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.   Ben Watson
  6.   Handle codeforces : quangminh98
  7.  
  8.   Mua Code nhu mua Florentino !!
  9. */
  10.  
  11. #define ll long long
  12.  
  13. const string name = "test";
  14.  
  15. void solve();
  16. signed main()
  17. {
  18.     if (fopen((name + ".inp").c_str(), "r"))
  19.     {
  20.         freopen((name + ".inp").c_str(), "r", stdin);
  21.         freopen((name + ".out").c_str(), "w", stdout);
  22.     }
  23.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  24.  
  25.     solve();
  26.  
  27.     return 0;
  28. }
  29.  
  30. // main program
  31. bool wrap(int a, int x, int b) { return a <= x && x <= b; }
  32.  
  33. void solve()
  34. {
  35.     int n, m; cin >> n >> m;
  36.     set<pair<int, int>> se;
  37.     for (int i = 0; i < m; i++)
  38.     {
  39.         int x, y; cin >> x >> y;
  40.         if (x == y || abs(x - y) <= n)
  41.             continue;
  42.         se.insert({x, y});
  43.     }
  44.     vector<pair<int, int>> edges;
  45.     for (pair<int, int> it : se)
  46.     {
  47.         if (it.first < it.second)
  48.             edges.push_back({it.first, it.second});
  49.         else
  50.             edges.push_back({it.second, it.first});
  51.     }
  52.     m = edges.size();
  53.  
  54.     vector<pair<int, int>> coor(4 * n + 1, {0, 0});
  55.     for (int i = 1; i <= n; i++)
  56.         coor[i] = make_pair(0, n - i + 1);
  57.     for (int i = n + 1; i <= 2 * n; i++)
  58.         coor[i] = make_pair(i - n - 1, 0);
  59.     for (int i = 2 * n + 1; i <= 3 * n; i++)
  60.         coor[i] = make_pair(n, i - 2 * n - 1);
  61.     for (int i = 3 * n + 1; i <= 4 * n; i++)
  62.         coor[i] = make_pair(n - (i - 3 * n - 1), n);
  63.  
  64.     ll res = 2;
  65.     for (int i = 1; i < m; i++)
  66.     {
  67.         res++;
  68.         set<pair<long double, long double>> se;
  69.         int u = edges[i].first, v = edges[i].second;
  70.         long double a1 = (coor[v].second - coor[u].second) / (coor[v].first - coor[u].first);
  71.         long double b1 = (coor[u].second * coor[v].first - coor[u].first * coor[v].second) / (coor[v].first - coor[u].first);
  72.         for (int j = i - 1; j >= 0; j--)
  73.         {
  74.             int a = edges[j].first, b = edges[j].second;
  75.             if (edges[i].first == edges[j].first || edges[i].second == edges[j].second)
  76.                 continue;
  77.  
  78.             if (1ll * (u - a) * (b - v) > 0 || wrap(a, u, b) || wrap(a, v, b) || wrap(u, a, v) || wrap(u, b, v))
  79.             {
  80.                 long double x1 = coor[a].first, y1 = coor[a].second;
  81.                 long double x2 = coor[b].first, y2 = coor[b].second;
  82.                 long double a2 = (y2 - y1) / (x2 - x1);
  83.                 long double b2 = (y1 * x2 - x1 * y2) / (x2 - x1);
  84.  
  85.                 long double xxx = (b2 - b1) / (a1 - a2);
  86.                 long double yyy = (a1 * b2 - b1 * a2) / (a1 - a2);
  87.                 se.insert({xxx, yyy});
  88.             }
  89.         }
  90.         res += se.size();
  91.     }
  92.  
  93.     cout << res << '\n';
  94. }
  95.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/ZB1ew9
language:
C++14 (clang 8.0)
created:
18 hours 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!