Submission #397645

#	Time	Username	Problem	Language	Result	Execution time	Memory
397645		MrRobot_28	Geometrija (COCI21_geometrija)	C++17	110 / 110	198 ms	16068 KiB

geometrija

#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];
    int cnt1[n][n];
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cnt1[i][j] = 0;
            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++;
            }
            cnt1[i][t[j].Y] = (n - 1 + j) - 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 f = cnt1[i][j];
            int f1 = n - 2 - f;
            d -= f * (f - 1) / 2;
            d -= f1 * (f1 - 1) / 2;
      //      cout << d << " ";
            if(d == (n - 2) * (n - 3) / 2)
            {
                ans++;
            }
        }
        //cout << "\n";
    }
    cout << ans;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60