Submission #397644

#TimeUsernameProblemLanguageResultExecution timeMemory
397644MrRobot_28Geometrija (COCI21_geometrija)C++17
50 / 110
1083 ms8176 KiB
#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define int long long #define sz(a) (int)a.size() const int mod = 1e9 + 7; const int N = 2e5+ 100; int crossproduct(pair <int, int> a, pair <int, int> b) { return a.X * b.Y - a.Y * b.X; } bool cmp(pair <pair <int, int>, int> a, pair <pair <int, int>, int> b) { if(a.X.X * b.X.X < 0) { return a.X.X > b.X.X; } if(a.X.X == 0) { return b.X.X < 0 || a.X.Y > 0; } if(b.X.X == 0) { return a.X.X > 0 && b.X.Y < 0; } return crossproduct(a.X, b.X) < 0; } signed main() { // ifstream cin("input1.txt.4c"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector <pair <int, int> > x(n); int cnt[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cnt[i][j] = 0; } } for(int i = 0; i < n; i++) { cin >> x[i].X >> x[i].Y; } vector <int> coun(n); for(int i = 0; i < n; i++) { vector <pair <pair <int, int>, int> > t; for(int j = 0; j < n; j++) { if(i != j) { t.push_back({{x[j].X - x[i].X, x[j].Y - x[i].Y}, j}); } } sort(t.begin(), t.end(), cmp); int it = 0; //cout << i << "\n"; for(int j = 0; j < n - 1; j++) { // cout << t[j].X.X << " " << t[j].X.Y << " " << t[j].Y << "\n"; while(it != n - 1 + j && (j == it || crossproduct(t[j].X, t[it % (n - 1)].X) < 0)) { it++; } // cout << "A " << it << " "; coun[j] = (n - 1 + j) - it; //cout << coun[j] << "\n"; } int sum = 0; it = 1; for(int j = 1; j < n - 1; j++) { sum += coun[j]; } for(int j = 0; j < n - 1; j++) { while(it != n - 1 + j && (it <= j || crossproduct(t[j].X, t[it % (n - 1)].X) < 0)) { sum -= coun[it % (n - 1)]; it++; } int k = it - j - 1; // cout << i << " " << t[j].Y << " " << sum + k * (k - 1) / 2 << "\n"; cnt[i][t[j].Y] += sum + k * (k - 1) / 2; sum += coun[j]; } } int ans = 0; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { int d = cnt[i][j] + cnt[j][i]; int k1 = 0, k2 = 0; int A = x[j].Y - x[i].Y; int B = x[i].X - x[j].X; int C = -x[i].X * A - x[i].Y * B; for(int t = 0; t < n; t++) { if(A * x[t].X + B * x[t].Y + C < 0) { k1++; } else if(A * x[t].X + B * x[t].Y + C > 0) { k2++; } } d -= k1 * (k1 - 1) / 2; d -= k2 * (k2 - 1) / 2; // cout << d << " "; if(d == (n - 2) * (n - 3) / 2) { ans++; } } //cout << "\n"; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...