Pagini recente » Cod sursa (job #1361577) | Cod sursa (job #57577) | Cod sursa (job #2658697) | Cod sursa (job #3259427) | Cod sursa (job #429478)
Cod sursa(job #429478)
#include<fstream>
#define dmax 1002
#define dmax2 1001000
using namespace std;
int n,nr,numar;
int x[dmax],y[dmax];
int pantasus[dmax2],pantajos[dmax2];
void generare()
{
int 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];
}
}
int coef(int a, int b)
{
if (a*b>=0)
return 1;
return -1;
}
int divide(int st, int dr)
{
int 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(int p, int q)
{
int m=divide(p,q);
if (m-1>p)
qsort(p,m-1);
if (m+1<q)
qsort(m+1,q);
}
int comb (int n, int k)
{
int 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()
{
int 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()
{
int 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;
}