Pagini recente » Cod sursa (job #1133294) | Cod sursa (job #1659545) | Cod sursa (job #478464)
Cod sursa(job #478464)
#include<fstream>
#define dmax 1005
#define dmax2 1001000
using namespace std;
long long n,x[dmax],y[dmax],k,px[dmax2],py[dmax2],paralelox,paraleloy;
long long total;
void pante()
{
long long i,j,auxx,auxy;
for (i=1; i<n; i++)
for (j=i+1; j<=n; j++)
{
auxx=x[j]-x[i];
auxy=y[j]-y[i];
if (auxx==0)
paraleloy++; else
if (auxy==0)
paralelox++; else
{
k++;
px[k]=auxx;
py[k]=auxy;
}
if ((px[k]<0 && py[k]<0) || (py[k]<0))
{
px[k]=px[k]*(-1);
py[k]=py[k]*(-1);
}
}
}
long long divide(long long st, long long dr)
{
long long x=px[st], y=py[st];
while (st<dr)
{
while (st<dr && px[dr]*y>=py[dr]*x)
dr--;
px[st]=px[dr];
py[st]=py[dr];
while (st<dr && px[st]*y<=py[st]*x)
st++;
px[dr]=px[st];
py[dr]=py[st];
}
px[st]=x;
py[st]=y;
return st;
}
void qsort(long long st, long long dr)
{
long long m=divide(st,dr);
if (m-1>st)
qsort(st,m-1);
if (m+1<dr)
qsort(m+1,dr);
}
long long comb(long long n)
{
if (n==2)
return 1; else
return ((n-1)*n)/2;
}
void numarare()
{
long long i,nr=1;
if (paralelox > 1)
total+=comb(paralelox);
if (paraleloy > 1)
total+=comb(paraleloy);
for (i=2; i<=k; i++)
if (px[i-1]*py[i] == py[i-1]*px[i])
nr++; else
{
if (nr>1)
total+=comb(nr);
nr=1;
}
if (nr>1)
total+=comb(nr);
}
int main()
{
long long i;
ifstream fin("trapez.in");
fin>>n;
for (i=1; i<=n; i++)
fin>>x[i]>>y[i];
pante();
qsort(1,k);
numarare();
ofstream fout("trapez.out");
fout<<total;
fin.close();
fout.close();
return 0;
}