Cod sursa(job #1029337)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 15 noiembrie 2013 13:10:18
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#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

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 ( abs ( 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 ("source.txt", "r");
	FILE *g = fopen ("text.txt", "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;
}