Pagini recente » Cod sursa (job #651423) | Cod sursa (job #1607580) | Cod sursa (job #535710) | Cod sursa (job #1571265) | Cod sursa (job #1029353)
#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>
#include<cstdlib>
using namespace std;
#define MAXN 1501
#define radical3 1.73205081
#define MAXDIFF 2000000000
double errorPrecision = 10e-4;
struct point
{
double x; double 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 0;
}
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, "%lf %lf", &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++)
{
Q.x = ( p[i].x + p[i].y * radical3 + p[j].x - p[j].y * radical3 ) / 2;
Q.y = ( -p[i].x * radical3 + p[i].y + p[j].y + p[j].x * radical3 ) / 2;
if (binSearch(0, n-1, Q) == 1);
nrTriang++;
Q.x = ( p[i].x + p[j].x + (p[j].y - p[i].y) * radical3 ) / 2;
Q.y = ( p[i].x * radical3 + p[j].y + p[i].y - p[j].x * radical3 ) / 2;
if ( binSearch(0, n-1, Q) == 1)
nrTriang++;
}
}
fprintf(g, "%d", nrTriang / 3);
fclose(f); fclose(g);
return 0;
}