Pagini recente » Cod sursa (job #486002) | Cod sursa (job #120715) | Cod sursa (job #681700) | Cod sursa (job #318921) | Cod sursa (job #1083015)
#include <cstdio>
#include <algorithm>
#define rad3 1.73205081
FILE *f,*g;
using namespace std;
typedef struct punct{
double x;
double y;
}pct;
pct p[1500];
double eps=10e-4;
int cmp(pct a, pct b)
{
if(a.x-b.x < eps && a.x-b.x > -eps)
{
if(a.y-b.y < eps && a.y-b.y > -eps)
return 0;
else
if(a.y-b.y > eps)
return 1;
else return -1;
}
if(a.x-b.x > eps)
return 1;
return -1;
}
void quicksort(int left, int right)
{
int i=left, j=right;
double tmpo;
pct tmp, piv;
piv = p[(left + right) / 2];
while(i<=j)
{
while(p[i].x < piv.x)
i++;
while(p[j].x > piv.x)
j--;
if(i<=j)
{
tmp = p[i];
p[i] = p[j];
p[j] = tmp;
if(p[i].x == p[j].x)
{
if(p[i].y > p[j].y)
{
tmpo=p[i].y;
p[i].y=p[j].y;
p[j].y=tmpo;
}
}
i++;
j--;
}
}
if(left<j)
quicksort(left,j);
if(i<right)
quicksort(i,right);
}
int caut(pct r, int left, int right)
{
int m;
if(left<=right)
{
m=(left+right)/2;
if(cmp(p[m],r)==0)
return 1;
else
if(cmp(p[m],r)<0)
return caut(r,m+1,right);
else
return caut(r,left,m-1);
}
else return 0;
}
int main()
{
int n,i,j;
double x1, y1;
f=fopen("triang.in","r");
g=fopen("triang.out","w");
fscanf(f,"%d",&n);
pct aux;
for(i=0;i<n;i++)
fscanf(f,"%lf %lf",&p[i].x,&p[i].y);
quicksort(0,n-1);
int nr=0;
for(i=0 ; i<n-1 ; i++)
{
for(j=i+1 ; j<n ; j++)
{
x1 = p[i].x + p[i].y * rad3 + p[j].x - p[j].y * rad3;
y1 = -p[i].x * rad3 + p[i].y + p[j].y + p[j].x * rad3;
aux.x = x1 / 2.0;
aux.y = y1 / 2.0;
if(caut(aux,0,n-1) == 1)
nr++;
x1 = p[i].x + p[j].x + (p[j].y - p[i].y) * rad3;
y1 = p[i].x * rad3 + p[j].y + p[i].y - p[j].x * rad3;
aux.x = x1 / 2.0;
aux.y = y1 / 2.0;
if(caut(aux,0,n-1) == 1)
nr++;
}
}
fprintf(g,"%d",nr/3);
fclose(f);
fclose(g);
return 0;
}