Pagini recente » Cod sursa (job #1032441) | Cod sursa (job #1294768) | Cod sursa (job #1991837) | Cod sursa (job #989564) | Cod sursa (job #383600)
Cod sursa(job #383600)
#include <stdio.h>
#include <algorithm>
using namespace std;
struct punct
{
int x,y;
};
struct muchie
{
int x,y;
};
punct v[1005],pct1,pct2,pct3,pct4;
muchie a[1000005];
int n,i,j,x,y,m,cadran,vechi,xv,yv,nr1,nr2,aux,k;
double dify1,difx1,dify2,difx2;
long long sol;
bool ok;
struct cmp
{
bool operator()(const muchie &m1,const muchie &m2)const
{
if (v[m1.x].y<v[m1.y].y)
{
pct1=v[m1.x];
pct2=v[m1.y];
}
else
{
pct1=v[m1.y];
pct2=v[m1.x];
}
if (v[m2.x].y<v[m2.y].y)
{
pct3=v[m2.x];
pct4=v[m2.y];
}
else
{
pct3=v[m2.y];
pct4=v[m2.x];
}
dify1=pct2.y-pct1.y;
dify2=pct4.y-pct3.y;
if (pct1.x<pct2.x)
difx1=pct2.x-pct1.x;
else
difx1=pct1.x-pct2.x;
if (pct3.x<pct4.x)
difx2=pct4.x-pct3.x;
else
difx2=pct3.x-pct4.x;
if (pct2.x<pct1.x && pct4.x<pct3.x)
if (dify1/difx1>dify2/difx2)
return 0;
else
return 1;
else
if (pct2.x>pct1.x && pct4.x>pct3.x)
if (dify1/difx1>dify2/difx2)
return 1;
else
return 0;
else
if (pct2.x<pct1.x && pct4.x>pct3.x)
return 1;
else
if (pct2.x>pct1.x && pct4.x<pct3.x)
return 0;
else
if (pct2.x==pct1.x)
return 0;
else
if (pct3.x==pct4.x)
return 1;
else
if (pct1.y==pct2.y)
return 1;
else
return 0;
}
};
int main()
{
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);
for (i=1;i<n;++i)
for (j=i+1;j<=n;++j)
{
++m;
a[m].x=i;
a[m].y=j;
}
sort(a+1,a+m+1,cmp());
for (i=1;i<=m;++i)
{
if (v[a[i].x].y>v[a[i].y].y)
{
pct1=v[a[i].y];
pct2=v[a[i].x];
}
else
{
pct1=v[a[i].x];
pct2=v[a[i].y];
}
if (pct2.x<pct1.x)
cadran=2;
else
cadran=1;
x=abs(pct1.x-pct2.x);
y=pct2.y-pct1.y;
nr1=x;
nr2=y;
while (nr2)
{
aux=nr1;
nr1=nr2;
nr2=aux%nr2;
}
x=x/nr1;
y=y/nr1;
if (cadran==vechi)
{
if (x==xv && y==yv)
ok=true;
else
ok=false;
}
else
ok=false;
if (ok)
++k;
else
{
sol+=(k-1)*k/2;
xv=x;
yv=y;
vechi=cadran;
k=1;
}
}
printf("%lld",sol+(k-1)*k/2);
return 0;
}