Cod sursa(job #483834)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 10 septembrie 2010 13:23:10
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#define Nmax 1002
#define LL long long
#include <algorithm>
#define INF 2147000000

using namespace std;

struct pxy{ int x,y,sp; } P[Nmax*Nmax],V[Nmax];
int N,NP;
LL nr,sol;

inline int cmp( pxy a, pxy b ){
	return ( a.x<b.x || (a.x==b.x && a.y<b.y) );
}
inline int cmp2( pxy a, pxy b ){
	return a.sp<b.sp || (a.sp==b.sp &&  a.y*b.x < b.y*a.x );
}	

int main(){
	int i,j;
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	scanf("%d",&N);
	for(i=1;i<=N;++i) scanf("%d%d",&V[i].x,&V[i].y);
	sort(V+1,V+N+1,cmp);
	
	for(i=1;i<N;++i)
		for(j=i+1;j<=N;++j){
			P[++NP].x=V[j].x-V[i].x, P[NP].y=V[j].y-V[i].y;
			P[NP].sp= (P[NP].x > 0 ? 1:-1) * (P[NP].y > 0 ? 1:-1);
		}
	sort(P+1,P+NP+1,cmp2);
	
	P[0].x=INF-1; P[0].y=INF;
	for(i=1;i<=NP; ){
		nr=1;
		if((LL)P[i-1].y*P[i].x == (LL)P[i-1].x*P[i].y )
			while( (LL)P[i-1].y*P[i].x == (LL)P[i-1].x*P[i].y &&i<=NP )
				++nr, ++i;
		else ++i;
		sol += nr*(nr-1)/2;
	}
	
	printf("%lld\n",sol);
	fclose(stdin); fclose(stdout);
	return 0;
}