Cod sursa(job #2774676)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 septembrie 2021 12:01:54
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct E {
    long long c,d;
};
E e[1001001];
int n,a[1001],b[1001],l,t,p,r,q,i,j;
int C(E a,E b)
{
    return a.c*b.d<a.d*b.c;
}
int main()
{
	freopen("trapez.in","r",stdin),freopen("trapez.out","w",stdout),scanf("%d",&n);
	for(i=1;i<=n;++i)
      	scanf("%d%d",a+i,b+i);
	for(i=1;i<n;++i)
        for(j=i+1;j<=n;++j) {
            if(b[j]==b[i])
                ++p;
            if(a[j]==a[i])
                ++r;
            if(b[j]!=b[i]&&a[j]!=a[i])
                e[++l].c=b[j]-b[i],e[l].d=a[j]-a[i];
        }
	for(i=1;i<=l;++i)
        if(e[i].d<0)
            e[i].c=-e[i].c,e[i].d=-e[i].d;
	sort(e+1,e+l+1,C);
	for(i=1;i<l;++i)
        if(e[i].c*e[i+1].d==e[i+1].c*e[i].d)
            ++t;
        else
            q=q+t*(t+1)/2,t=0;
	if(t)
      	q=q+t*(t+1)/2;
	printf("%d",q+p*(p-1)/2+r*(r-1)/2);
	return 0;
}