Cod sursa(job #334616)
#include <algorithm>
#include <math.h>
using namespace std;
#define DIM 1505
#define EPS 0.001
struct punct {double x,y;} a[DIM];
double psin,pcos;
int n,nrt;
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
scanf ("%lf%lf",&a[i].x,&a[i].y);
}
int cmp (punct a,punct b)
{
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
double fabs (double a)
{
if (a<0)
return -a;
return a;
}
int check (punct a,punct b)
{
if (fabs (a.x-b.x)<EPS)
{
if (fabs (a.y-b.y)<EPS)
return 0;
else if (a.y>b.y)
return -1;
else
return 1;
}
else if(a.x>b.x)
return -1;
else
return 1;
}
int cbin (punct p)
{
int st,dr,mij,ok;
for (st=1, dr=n; 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 ()
{
punct p;
int i,j;
psin=(double)sqrt (3)/2;
pcos=(double)1/2;
for (i=1; i<n; ++i)
for (j=i+1; j<=n; ++j)
{
p.x=(a[j].x-a[i].x)*pcos-(a[j].y-a[i].y)*psin+a[i].x;
p.y=(a[j].x-a[i].x)*psin+(a[j].y-a[i].y)*pcos+a[i].y;
nrt+=cbin (p);
p.x=(a[i].x-a[j].x)*pcos-(a[i].y-a[j].y)*psin+a[j].x;
p.y=(a[i].x-a[j].x)*psin+(a[i].y-a[j].y)*pcos+a[j].y;
nrt+=cbin (p);
}
printf ("%d",nrt/3);
}
int main ()
{
freopen ("triang.in","r",stdin);
freopen ("triang.out","w",stdout);
read ();
sort (a+1,a+n+1,cmp);
solve ();
return 0;
}