Cod sursa(job #334614)
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define EPS 0.001
vector <pair <double,double> > a;
double psin,pcos;
int n,nrt;
void read ()
{
double x,y;
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
{
scanf ("%lf%lf",&x,&y);
a.pb (mp (x,y));
}
}
double fabs (double a)
{
if (a<0)
return -a;
return a;
}
int check (pair <double,double> a,pair <double,double> b)
{
if (fabs (a.fs-b.fs)<EPS)
{
if (fabs (a.sc-b.sc)<EPS)
return 0;
else if (a.sc>b.sc)
return -1;
else
return 1;
}
else if(a.fs>b.fs)
return -1;
else
return 1;
}
int cbin (pair <double,double> p)
{
int st,dr,mij,ok;
for (st=0, dr=n-1; st<=dr; )
{
mij=(st+dr)/2;
ok=check (p,a[mij]);
if (!ok)
return 1;
else if (ok<0)
st=mij+1;
else
dr=mij-1;
}
return 0;
}
void solve ()
{
pair <double,double> p;
int i,j;
psin=(double)sqrt (3)/2;
pcos=(double)1/2;
for (i=0; i<n-1; ++i)
for (j=i+1; j<n; ++j)
{
p.fs=(a[j].fs-a[i].fs)*pcos-(a[j].sc-a[i].sc)*psin+a[i].fs;
p.sc=(a[j].fs-a[i].fs)*psin+(a[j].sc-a[i].sc)*pcos+a[i].sc;
nrt+=cbin (p);
p.fs=(a[i].fs-a[j].fs)*pcos-(a[i].sc-a[j].sc)*psin+a[j].fs;
p.sc=(a[i].fs-a[j].fs)*psin+(a[i].sc-a[j].sc)*pcos+a[j].sc;
nrt+=cbin (p);
}
printf ("%d",nrt/3);
}
int main ()
{
freopen ("triang.in","r",stdin);
freopen ("triang.out","w",stdout);
read ();
sort (a.begin (),a.end ());
solve ();
return 0;
}