Dang_Quan_10_Tin

ĐA GIÁC BAO

Nov 8th, 2022
956
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #define task ""
  6. using namespace std;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. const int N = 2.5e3 + 2;
  11. int n;
  12. struct Vector
  13. {
  14.     ll x, y;
  15.     Vector(int x = 0, int y = 0)
  16.     {
  17.         this->x = x;
  18.         this->y = y;
  19.     }
  20.     Vector operator-(const Vector &a) const
  21.     {
  22.         Vector ans;
  23.         ans.x = x - a.x;
  24.         ans.y = y - a.y;
  25.         return ans;
  26.     }
  27.     ll operator*(const Vector &a)
  28.     {
  29.         return x * a.y - y * a.x;
  30.     }
  31.     bool operator<(const Vector &a) const
  32.     {
  33.         bool ck1 = x < 0 || (x == 0 && y < 0),
  34.              ck2 = a.x < 0 || (a.x == 0 && a.y < 0);
  35.         if (ck1 != ck2)
  36.             return ck1 < ck2;
  37.         return (x * a.y - y * a.x) > 0;
  38.     }
  39. } a[N];
  40.  
  41. void Read()
  42. {
  43.     cin >> n;
  44.     for (int i = 1; i <= n; ++i)
  45.         cin >> a[i].x >> a[i].y;
  46. }
  47.  
  48. ll C3(ll v)
  49. {
  50.     return v * (v - 1) * (v - 2) / 6;
  51. }
  52.  
  53. ll C5(ll v)
  54. {
  55.     return v * (v - 1) * (v - 2) * (v - 3) * (v - 4) / 120;
  56. }
  57.  
  58. void Solve()
  59. {
  60.     ll ans(0);
  61.     for (int i = 1; i <= n; ++i)
  62.     {
  63.         // cout << i << ":\n";
  64.         vector<Vector> s;
  65.         for (int j = 1; j <= n; ++j)
  66.             if (i != j)
  67.                 s.push_back(a[j] - a[i]);
  68.         sort(s.begin(), s.end());
  69.         int t = 0;
  70.         for (int j = 0; j < (int)s.size(); ++j)
  71.         {
  72.             while (t < j + (int)s.size() && s[j] * s[t % s.size()] >= 0)
  73.                 ++t;
  74.             //cout << j << " " << t << "\n";
  75.             ans += C3(t - j - 1);
  76.         }
  77.     }
  78.     cout << C5(n) * 5 - ans;
  79. }
  80.  
  81. int32_t main()
  82. {
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0);
  85.     cout.tie(0);
  86.     if (fopen(task ".INP", "r"))
  87.     {
  88.         freopen(task ".INP", "r", stdin);
  89.         freopen(task ".OUT", "w", stdout);
  90.     }
  91.     Read();
  92.     Solve();
  93. }
Advertisement
Comments
Add Comment
Please, Sign In to add comment