Pagini recente » Cod sursa (job #2906421) | numere9 | Profil selenahurloi | Cod sursa (job #2981949) | Cod sursa (job #286145)
Cod sursa(job #286145)
#include <cstdio>
#include <math.h>
using namespace std;
#define Nmax 1024
int n, x[Nmax], y[Nmax], nr;
long long dx[Nmax*Nmax], dy[Nmax*Nmax];
int cmp(int i,int j)
{
long long p1,p2;
p1 = dy[i]*dx[j];
p2 = dy[j]*dx[i];
if (p1 == p2) return 0;
if (p1 < p2) return 1;
return -1;
}
void qsort(int st,int dr)
{
int i=st,j=dr;
long long tmp;
dx[0] = dx[(i+j)/2];
dy[0] = dy[(i+j)/2];
do
{
while (cmp(i,0) == 1) ++i;
while (cmp(0,j) == 1) --j;
if (i<=j)
{
tmp = dx[i];
dx[i] = dx[j];
dx[j] = tmp;
tmp = dy[i];
dy[i] = dy[j];
dy[j] = tmp;
++i; --j;
}
} while (i<=j);
if (st<j) qsort(st,j);
if (i<dr) qsort(i,dr);
}
int main()
{
freopen("trapez.in","r",stdin);
freopen("trapez.out","w",stdout);
scanf("%d", &n);
for (int i=1;i<=n;++i)
{
scanf("%d%d", x+i,y+i);
for (int j=1;j<i;++j)
{
++nr;
dx[nr] = (long long)x[i]-(long long)x[j]+1;
dy[nr] = (long long)y[i]-(long long)y[j]+1;
}
}
long long tmp = 1, ret = 0, a,b,c;
for (int i=1;i<=nr;++i)
if (cmp(i,i-1))
{
a = tmp;
b = a-1;
c = a*b;
c = c/2;
if (c>0)
ret += c;
tmp = 1;
}
else
++tmp;
a = tmp;
b = a-1;
c = a*b;
c = c/2;
if (c>0)
ret += c;
printf("%lld\n", ret);
return 0;
}