Pagini recente » Cod sursa (job #2480527) | Cod sursa (job #1068042) | Cod sursa (job #1651425) | Cod sursa (job #1731461) | Cod sursa (job #1033137)
#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.7320508075
#define MAXDIFF 2000000000
#define PI 3.141592653
double eps = 1e-3;
struct point
{
double x, y;
};
point p[MAXN];
int n;
point obt(point A, point B)
{
point I;
I.x = A.x + (cos(PI / 3.0)) * (B.x - A.x) - (sin(PI / 3.0)) * (B.y - A.y);
I.y = A.y + (sin(PI / 3.0)) * (B.x - A.x) + (cos(PI / 3.0)) * (B.y - A.y);
return I;
}
int cmp(double a, double b) {
if(a + eps < b) return -1;
if(b + eps < a) return 1;
return 0;
}
int isTriangle(point a, point b)
{
if(cmp(a.x, b.x) == 0)
{
return cmp(a.y, b.y);
}
return cmp(a.x, b.x);
}
/*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 binSearch(point r) {
int pos = 0;
for(int i = 1<<30; i > 0; i >>= 1) {
if(pos + i < n && isTriangle (p[pos + i], r) < 1) {
pos += i;
}
}
return isTriangle(r, p[pos]) == 0;
}
int compare (void const *a, void const *b)
{
return ( *(double*)a - *(double*)b );
}
int main()
{
FILE *f = fopen ("triang.in", "r");
FILE *g = fopen ("triang.out", "w");
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 = obt(p[i], p[j]);
if (binSearch(Q) == 1);
nrTriang++;
Q = obt(p[j], p[i]);
if ( binSearch(Q) == 1)
nrTriang++;
}
}
fprintf(g, "%d", nrTriang / 3);
fclose(f); fclose(g);
return 0;
}