Pagini recente » Cod sursa (job #2077211) | Cod sursa (job #1816239) | Cod sursa (job #1193740) | Cod sursa (job #943660) | Cod sursa (job #429547)
Cod sursa(job #429547)
#include<fstream>
#define dmax 1002
#define dmax2 1001000
using namespace std;
long n,nr,numar,ox,oy;
long x[dmax],y[dmax];
long pantasus[dmax2],pantajos[dmax2];
void generare()
{
long i,j;
long pantasusaux,pantajosaux;
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
{
pantasusaux=x[i]-x[j];
pantajosaux=y[i]-y[j];
if (pantasusaux==0)
oy++; else
if (pantajosaux==0)
ox++; else
{
nr++;
pantasus[nr]=pantasusaux;
pantajos[nr]=pantajosaux;
}
}
}
long coef(long a, long b)
{
if (a*b>=0)
return 1;
return -1;
}
long divide(long st, long dr)
{
long x=pantasus[st],y=pantajos[st];
while (st<dr)
{
while (st<dr && y*pantasus[dr]>=x*pantajos[dr]*coef(y,pantajos[dr]))
dr--;
pantasus[st]=pantasus[dr];
pantajos[st]=pantajos[dr];
while (st<dr && y*pantasus[st]<=x*pantajos[st]*coef(y,pantajos[st]))
st++;
pantasus[dr]=pantasus[st];
pantajos[dr]=pantajos[st];
}
pantasus[st]=x;
pantajos[st]=y;
return st;
}
void qsort(long p, long q)
{
long m=divide(p,q);
if (m-1>p)
qsort(p,m-1);
if (m+1<q)
qsort(m+1,q);
}
long comb (long n, long k)
{
long i,nr1=1,nr2=1,nr3=1;
for (i=2; i<=n; i++)
{
nr1=nr1*i;
if (i<=n-k)
nr2=nr2*i;
if (i<=k)
nr3=nr3*i;
}
return nr1/(nr2=nr3);
}
void numarare()
{
long i,pi,pf;
pi=1; pf=1;
for (i=2; i<=nr; i++)
if (pantasus[i]*pantajos[i-1]==pantasus[i-1]*pantajos[i])
pf++; else
{
if (pf!=pi)
numar=numar+comb(pf-pi+1,2);
pi=i; pf=i;
}
if (ox>1)
numar=numar+comb(ox,2);
if (oy>1)
numar=numar+comb(oy,2);
}
int main()
{
long i;
ifstream fin("trapez.in");
fin>>n;
for (i=1; i<=n; i++)
fin>>x[i]>>y[i];
generare();
qsort(1,nr);
numarare();
ofstream fout("trapez.out");
fout<<numar;
fin.close();
fout.close();
return 0;
}