Pagini recente » Cod sursa (job #38437) | Cod sursa (job #2543552) | Cod sursa (job #3255769) | Cod sursa (job #2448548) | Cod sursa (job #42770)
Cod sursa(job #42770)
#include <stdio.h>
#include <math.h>
int N, step;
long Sol;
struct Punct
{ double x, y; } A[1501];
void Read();
void Solve();
void Write();
int bsearch(int, int, double);
int ok(double, double);
double d(Punct, Punct);
int main()
{
Read();
Solve();
Write();
return 0;
}
void Read()
{
freopen("triang.in", "r", stdin);
scanf("%d", &N);
int i;
for(i=1; i<=N; ++i)
{
scanf("%lf %lf", &A[i].x, &A[i].y);
float x1;
A[i].x *= 1000;
x1 = (int) A[i].x;
A[i].x = x1 / 1000;
A[i].y *= 1000;
x1 = (int) A[i].y;
A[i].y = x1 / 1000;
}
fclose(stdin);
}
void Solve()
{
int i, j, k, l, found;
double dist;
for(i=1; i<N; ++i)
for(j=i+1; j<=N; ++j)
if(A[i].x > A[j].x || (A[i].x == A[j].x && A[i].y > A[j].y))
{
Punct aux;
aux = A[i];
A[i] = A[j];
A[j] = aux;
}
for(i=1; i<=N-2; ++i)
for(j=i+2; j<=N; ++j)
{
k = bsearch(i+1, j, (A[i].x+A[j].x)/2);
dist = d(A[i], A[j]);
if(k)
{
found = 0;
for(l=k; l<=j&&A[l].x==A[k].x; ++l)
if(ok(d(A[l], A[i]), dist) && ok(d(A[l], A[j]), dist))
{
found = 1;
break;
}
Sol += found;
}
}
}
void Write()
{
freopen("triang.out", "w", stdout);
printf("%ld", Sol);
fclose(stdout);
}
int bsearch(int l, int r, double value)
{
int n = (r-l+1), step, i;
for(step=1; step<=n; step<<=1);
for(i=l; step; step>>=1)
if(i+step <= r && A[i+step].x <= value)
i += step;
if(A[i].x == value)
return i;
return 0;
}
double d(Punct A, Punct B)
{
return
sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
int ok(double a, double b)
{
double c, y;
int x;
c = a > b ? a - b : b - a;
x = (int) (c * 1000);
y = x;
c = y / 1000;
return !c;
}