Pagini recente » Cod sursa (job #2722311) | Cod sursa (job #1121781) | Cod sursa (job #1238191) | Cod sursa (job #458378) | Cod sursa (job #42388)
Cod sursa(job #42388)
#include <stdio.h>
#include <math.h>
int N;
long Sol;
struct Punct
{ double x, y; } A[1501];
void Read();
void Solve();
void Write();
int b_search(Punct, Punct, int, int);
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);
fclose(stdin);
}
void Solve()
{
int i, j;
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+1; j<=N-1; ++j)
{
if(b_search(A[i], A[j], j+1, N))
++ Sol;
}
}
void Write()
{
freopen("triang.out", "w", stdout);
printf("%ld", Sol);
fclose(stdout);
}
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 b_search(Punct X, Punct Y, int ls, int ld)
{
int m;
while(ls <= ld)
{
m = (ls + ld) >> 1;
float a = d(X, Y), b = d(X, A[m]), dif;
dif = b - a;
dif *= dif < 0 ? -1 : 1;
int x = (int) (dif * 1000);
float y = x;
dif = y / 1000;
if(!dif) return 1;
else
{
if(d(X, A[m]) < d(X, Y))
ls = m + 1;
if(d(X, A[m]) > d(X, Y))
ld = m - 1;
}
}
return 0;
}