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)
  41.             continue;
  42.         if (x > y) swap(x, y);
  43.         if (x % n == 1 && abs(x - y) <= n)
  44.             continue;
  45.         if (x == 1 && y >= 3 * n + 1)
  46.         {
  47.             continue;
  48.         }
  49.  
  50.         se.insert({x, y});
  51.     }
  52.     vector<pair<int, int>> edges;
  53.     for (pair<int, int> it : se)
  54.     {
  55.         if (it.first < it.second)
  56.             edges.push_back({it.first, it.second});
  57.         else
  58.             edges.push_back({it.second, it.first});
  59.     }
  60.     m = edges.size();
  61.  
  62.     vector<pair<int, int>> coor(4 * n + 1, {0, 0});
  63.     for (int i = 1; i <= n; i++)
  64.         coor[i] = make_pair(0, n - i + 1);
  65.     for (int i = n + 1; i <= 2 * n; i++)
  66.         coor[i] = make_pair(i - n - 1, 0);
  67.     for (int i = 2 * n + 1; i <= 3 * n; i++)
  68.         coor[i] = make_pair(n, i - 2 * n - 1);
  69.     for (int i = 3 * n + 1; i <= 4 * n; i++)
  70.         coor[i] = make_pair(n - (i - 3 * n - 1), n);
  71.  
  72.     ll res = 2;
  73.     for (int i = 1; i < m; i++)
  74.     {
  75.         res++;
  76.         set<pair<long double, long double>> se;
  77.         int u = edges[i].first, v = edges[i].second;
  78.         long double a1 = (coor[v].second - coor[u].second) / (coor[v].first - coor[u].first);
  79.         long double b1 = (coor[u].second * coor[v].first - coor[u].first * coor[v].second) / (coor[v].first - coor[u].first);
  80.         for (int j = i - 1; j >= 0; j--)
  81.         {
  82.             int a = edges[j].first, b = edges[j].second;
  83.             if (edges[i].first == edges[j].first || edges[i].second == edges[j].second)
  84.                 continue;
  85.  
  86.             if (1ll * (u - a) * (b - v) > 0 || wrap(a, u, b) || wrap(a, v, b) || wrap(u, a, v) || wrap(u, b, v))
  87.             {
  88.                 long double x1 = coor[a].first, y1 = coor[a].second;
  89.                 long double x2 = coor[b].first, y2 = coor[b].second;
  90.                 long double a2 = (y2 - y1) / (x2 - x1);
  91.                 long double b2 = (y1 * x2 - x1 * y2) / (x2 - x1);
  92.  
  93.                 long double xxx = (b2 - b1) / (a1 - a2);
  94.                 long double yyy = (a1 * b2 - b1 * a2) / (a1 - a2);
  95.                 se.insert({xxx, yyy});
  96.             }
  97.         }
  98.         res += se.size();
  99.     }
  100.  
  101.     cout << res << '\n';
  102. }
  103.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/7eyD8B
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!