Submission #68364496

---

Source Code Expand

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
int read(){int f=0,x=0;char a=getchar();while(!isdigit(a)){if(a=='-')f=1;a=getchar();}while(isdigit(a)){x=x*10+a-'0';a=getchar();}if(f)return -x;return x;}
struct node
{
    ll x,y;
};
vector<node>a(2000+1);
struct nod
{
    ll a1,a2;
    friend bool operator<(nod c,nod d)
    {
        ll dx=a[c.a1].x-a[c.a2].x;
        ll dy=a[c.a1].y-a[c.a2].y;
        ll dxx=a[d.a1].x-a[d.a2].x;
        ll dyy=a[d.a1].y-a[d.a2].y;
        if(!dx&&dxx)
        {
            return 0;
        }
        if(!dxx&&dx)
        {
            return 1;
        }
        return dx*dyy<dxx*dy;
    }
};
int main()
{
    //freopen(in.in,r,stdin);
    //freopen(out.out,w,stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tttt=1;
    //cin>>tttt;
    while(tttt--)
    {
        ll n,ans=0;cin>>n;
        multiset<nod>q;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].x>>a[i].y;
        }
        sort(a.begin()+1,a.begin()+n+1,[](node c,node d){return c.x<d.x;});
        q.insert({2,1});
        q.insert({3,1});
        q.insert({3,2});
        // for(int i=1;i<=n;i++)
        // {
        //     cout<<a[i].x<<' '<<a[i].y<<'\n';
        // }
        for(int i=4;i<=n;i++)
        {
            bool yw=0;
            // for(auto j:q)
            // {
            //     cout<<j.a1<<' '<<j.a2<<'\n';
            // }
            for(int j=1;j<i;j++)
            {
                auto l=q.lower_bound({i,j});
                auto r=q.upper_bound({i,j});
                for(auto it=l;it!=r;it++)
                {
                    auto [p1,p2]=*it;
                    if(a[p1].x-a[p2].x==a[i].x-a[j].x&&a[p1].y-a[p2].y==a[i].y-a[j].y)
                    {
                        if(yw)
                        {
                            ans++;
                        }
                        yw=!yw;
                    }
                    else
                    {
                        ans++;
                    }
                    //cout<<i<<" "<<j<<" "<<p1<<" "<<p2<<' '<<yw<<'\n';
                }
            }
            for(int j=1;j<i;j++)
            {
                q.insert({i,j});
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Submission Info

Judge Result