Cod sursa(job #483688)

Utilizator cosmyoPaunel Cosmin cosmyo Data 9 septembrie 2010 18:53:49
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
const int NMAX=1005;
using namespace std;
struct punct{long x,y;};
long long rez,n,nr;
punct p[NMAX],o[NMAX*NMAX];
vector<punct> v;
void cit()
{ifstream fin("trapez.in");
  fin>>n;
  long i;
   for(i=1;i<=n;++i)
		fin>>p[i].x>>p[i].y;
  fin.close();
}
bool crt(punct a,punct b)
{long x1,y1,x2,y2;
 x1=(p[a.x].x-p[a.y].x);
 y1=(p[a.x].y-p[a.y].y);
 x2=(p[b.x].x-p[b.y].x);
 y2=(p[b.x].y-p[b.y].y);
 return y1*x2<x1*y2;
}
ofstream fout("trapez.out");
void solve()
{long i,j;
 long long k;
 long x1,y1,x2,y2;
 punct a,b;
  for(i=1;i<=n;++i)
	  for(j=i+1;j<=n;++j)
	   if(p[i].x==p[j].x)
		   {a.x=i;a.y=j;v.push_back(a);}
	   else
		o[++nr].x=i,o[nr].y=j;
 sort(o+1,o+nr+1,crt);
 k=1;
 for(i=1;i<=nr-1;++i)
    {a=o[i];b=o[i+1];
	 x1=(p[a.x].x-p[a.y].x);
     y1=(p[a.x].y-p[a.y].y);
     x2=(p[b.x].x-p[b.y].x);
     y2=labs(p[b.x].y-p[b.y].y);
	 if(y1*x2==x1*y2)
      ++k;
		else
		{rez=(long long)rez+(k*(k-1))/2;
		 k=1; 
		}
	}
 rez+=((v.size()-1)*(v.size()))/2;	
}
void afis()
{long i;
  fout<<rez<<'\n';
 fout.close();
}
int main()
{cit();
 solve();
 afis();
 return 0;
}