Cod sursa(job #1029303)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 15 noiembrie 2013 12:39:53
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 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>

using namespace std;
	
#define MAXN 1501
#define radical3 1.7320508075
#define MAXDIFF	2000000000
#define errorPrecision 0.0099999

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 ( 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 ("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; 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;
}