Pagini recente » Cod sursa (job #536697) | Cod sursa (job #691011) | Cod sursa (job #1366793) | Cod sursa (job #2376509) | Cod sursa (job #443094)
Cod sursa(job #443094)
#include<fstream>
using namespace std;
struct structura{int x,y;};
structura p[1001],v[500001],t,aux;
int n,poz,cm,nroy,nrox,s,nr;
int absolut(int a)
{
if(a<0)
a=-a;
return a;
}
int cmmdc(int a,int b)
{
while(a!=b)
{
if(absolut(a)>absolut(b)){a=a%b;if(a==0)a=b;}
else{b=b%a;if(b==0)b=a;}
}
return a;
}
void swap(structura a,structura b)
{
aux=a;a=b;b=aux;
}
void citire()
{
int i;
ifstream f("trapez.in");
f>>n;
for(i=1;i<=n;i++)
f>>p[i].x>>p[i].y;
}
void panta()
{
int i,j;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
t.x=p[j].x-p[i].x;t.y=p[j].y-p[i].y;
if(t.x!=0&&t.y!=0)
{
cm=cmmdc(t.y,t.x);
poz++;
v[poz].x=t.x/cm;v[poz].y=t.y/cm;
}
else if(t.y==0)nroy++;
else nrox++;
}
}
void DownHeap( int from, int to )
{
for( int son=2*from; son < to; from=son, son=2*from )
{
if( son < to-1 && v[son+1].y > v[son].y ||(v[son].y==v[son+1].y&&v[son+1].x>v[son].x))
++son;
if( v[from].y > v[son].y||(v[from].y==v[son].y&&v[from].x>=v[son].x) )
return;
swap( v[from], v[son] );
}
}
void HeapSort( int from, int to )
{
int i;
for( i=(to-from)/2; i >= 0; --i )
DownHeap( i, to );
while( to > from )
{
swap( v[from], v[to-1] );
--to;
DownHeap( from, to );
}
}
int main()
{
int i,j;
citire();
panta();
for(i=1;i<poz;i++)
for(j=i+1;j<=poz;j++)
if(v[j].y<v[i].y||(v[i].y==v[j].y&&v[j].x<v[i].x))
{
aux=v[i];v[i]=v[j];v[j]=aux;
}
aux=v[1];nr=1;s+=nroy*(nroy-1)/2;s+=nrox*(nrox-1)/2;
for(i=2;i<=poz;i++)
{
if(aux.x==v[i].x&&aux.y==v[i].y)
nr++;
else
{
aux=v[i];
s+=nr*(nr-1)/2;nr=1;
}
}
ofstream g("trapez.out");
g<<s<<'\n';
}