Cod sursa(job #591277)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 23 mai 2011 17:45:56
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb

#include <cstdio>
#include <fstream>
#include <algorithm>

using namespace std;

#define N 1<<11

struct trap {
	int x,y,z;
	bool friend operator < (const trap& a,const trap& b){
		if(a.z<b.z)return 1;
		if(a.z==b.z&&a.x<b.x)return 1;
		if(a.z==b.z&&a.x==b.x&&a.y<=b.y)return 1;
		return 0;}
	};
	
	trap a[N],b[N];
	
trap add (int a,int b,int c){
	trap h;
	h.x=a,h.y=b,h.z=c;
	return h;}

bool cmp (trap a,trap b){
		return a.x==b.x&&a.y==b.y&&a.z==b.z;}
	
inline int abs (int q){
	return q<0?q*(-1):q;}	
	
inline int cmmdc (int q,int w){
	if(!w)return q;
	return cmmdc(w,q%w);}
	
int main ()
{
	
	ifstream in ("trapez.in");
	freopen ("trapez.out","w",stdout);
	int n,m=0;
	in>>n;
	for(int i=1;i<=n;++i)
		in>>a[i].x>>a[i].y;
	for(int i=1;i<n;++i)
	for(int j=i+1;j<=n;++j){
		int q=a[i].x-a[j].x,
			w=a[i].y-a[j].y,s;
		if((w>=0&&q>=0)||(w<0&&q<0))
			s=0;
		else
			s=1;
		q=abs(q),w=abs(w);
		if(w!=0&&q!=0){
			int d=cmmdc(w,q);
			w/=d,q/=d;
			}
		else
			if(w)
				w=q=1;
			else
				w=q=0;
		b[++m]=add(w,q,s);
		}
	sort(b+1,b+m+1);
	trap k;
	int S=0;
	k.x=k.y=-1;
	int g=1;
	for(int i=1;i<=m;++i)
		if(cmp(b[i],k))
			++g;
		else{
			S+=((g*(g-1))>>1);
			k=b[i];
			g=1;
			}
	printf("%d",S);
	
	return 0;}