Pagini recente » Cod sursa (job #2796534) | Cod sursa (job #2980561) | Cod sursa (job #424686) | Cod sursa (job #131281) | Cod sursa (job #406637)
Cod sursa(job #406637)
#include<stdio.h>
#include<cmath>
#include<algorithm>
#define Nmx 1505
#define EPS 0.001
using namespace std;
struct coord
{
double x,y;
};
coord a[Nmx];
int n;
void citire()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
}
inline int cmp (coord a,coord b)
{
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
inline double fabs (double a)
{
if (a<0)
return -a;
return a;
}
inline int check(coord a,coord 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 caut(int st,int dr,coord p)
{
while(st<=dr)
{
int mij=(st+dr)>>1;
int ok=check (p,a[mij]);
if (!ok)
return 1;
else if (ok<0)
st=mij+1;
else
dr=mij-1;
}
return 0;
}
void solve()
{
int nr=0;
double psin=(double)sqrt (3)/2;
double pcos=(double)1/2;
coord p;
sort(a+1,a+n+1,cmp);
for(int i=1;i<n;++i)
for(int 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;
nr+=caut(j+1,n,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;
nr+=caut(j+1,n,p);
}
printf("%d\n",nr);
}
int main()
{
freopen("triang.in","r",stdin);
freopen("triang.out","w",stdout);
citire();
solve();
return 0;
}