Pagini recente » Cod sursa (job #1782479) | Cod sursa (job #3349049) | Cod sursa (job #287313) | Monitorul de evaluare | Cod sursa (job #1029329)
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
using namespace std;
#define MAXN 1501
#define radical3 1.7320508075
#define MAXDIFF 2000000000
double errorPrecision = 10e-4;
struct point
{
double x; double y;
};
inline double dist(point A, point B)
{
return ( (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) );
}
int compare (void const *a, void const *b)
{
return ( *(double*)a - *(double*)b );
}
point p[MAXN];
int isTriangle(point A, point B)
{
if ( abs ( A.x - B.x ) < errorPrecision )
{
if ( abs ( A.y - B.y ) < errorPrecision)
return 0;
else
if ( ( A.y - B.y ) > errorPrecision )
return 1;
else
return -1;
}
if ( (A.x - B.x) > errorPrecision )
return 1;
return -1;
}
int binSearch(int li, int ls, point A)
{
if ( li < ls )
{
int mid = ( li + ls ) / 2;
int result = isTriangle ( p[mid], A );
if (result == 0)
return 1;
else
if (result < 0)
return binSearch (mid + 1, ls, A);
else
return binSearch (li, mid-1, A);
}
else
return -1;
}
int main()
{
FILE *f = fopen ("triang.in", "r");
FILE *g = fopen ("triang.out", "w");
int n;
fscanf(f, "%d", &n);
for (int i = 0; i < n; i++)
fscanf(f, "%d", &p[i].x, &p[i].y);
qsort(p, n, sizeof(point), compare);
point Q;
int nrTriang = 0;
for (int i = 0; i < n-1; i++)
{
for (int j = i + 1; j < n; j++)
{
double d1 = dist(p[i], p[j]);
Q.x = ( -p[i].x + p[i].y * radical3 + p[j].x + p[j].y * radical3 ) / 2;
Q.y = ( -p[i].y - p[i].x * radical3 - p[j].x * radical3 + p[j].y ) / 2;
if (binSearch(0, n-1, Q) == 1);
nrTriang++;
}
}
fprintf(g, "%d", nrTriang / 3);
fclose(f); fclose(g);
return 0;
}