Pagini recente » Cod sursa (job #439923) | Cod sursa (job #2712781) | Cod sursa (job #2723501) | Cod sursa (job #1767859) | Cod sursa (job #429479)
Cod sursa(job #429479)
#include<fstream>
#define dmax 1002
#define dmax2 1001000
using namespace std;
long n,nr,numar;
long x[dmax],y[dmax];
long pantasus[dmax2],pantajos[dmax2];
void generare()
{
long i,j;
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
{
nr++;
pantasus[nr]=x[i]-x[j];
pantajos[nr]=y[i]-y[j];
}
}
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;
}
}
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;
}