Cod sursa(job #473037)

Utilizator robigiirimias robert robigi Data 27 iulie 2010 18:44:09
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
// Triang.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"
#include "math.h"

FILE *f=fopen("triang.in", "r");
FILE *g=fopen("triang.out", "w");

int n, nr;
double x[1501], y[1501];

void read()
{
	fscanf(f, "%d", &n);
	for (int i=1; i<=n; i++)
		fscanf(f, "%lf%lf", &x[i], &y[i]);
}


void quicksort(int lo, int hi)
{
	int i=lo, j=hi;
	double h;
	double m=x[(lo+hi)/2];
	do
	{
		while (x[i]<m) i++;
		while (x[j]>m) j--;
		if (i<=j)
		{
			h=x[i]; x[i]=x[j]; x[j]=h;
			h=y[i]; y[i]=y[j]; y[j]=h;
			i++; j--;
		}
	}while (i<=j);
	if (j>lo) quicksort(lo, j);
	if (i<hi) quicksort(i, hi);
}


void binar(double xx, double yy)
{
	int lo=1, hi=n;
	int mid=lo+(hi-lo)/2;;
	while (hi-lo>0 && fabs(x[mid]-xx)>0.001)
	{
		if (x[mid]>=xx || fabs(x[mid]-xx)<=0.001) hi=mid-1;
		else lo=mid+1;
		mid=lo+(hi-lo)/2;
	}
	if (fabs(x[mid]-xx)<=0.001)
	{
		int i=mid, j=mid;
		while (fabs(x[i]-xx)<=0.001 && fabs(y[i]-yy)>0.001)
			i--;
		if (fabs(x[i]-xx)<=0.001 && fabs(y[i]-yy)<=0.001) 
		{
			nr++; 
			return;
		}
		while (fabs(x[j]-xx)<=0.001 && fabs(y[j]-yy)>0.001)
			j++;
		if (fabs(x[j]-xx)<=0.001 && fabs(y[j]-yy)<=0.001) 
		{
			nr++; 
			return;
		}
	}
}


void program()
{
	for (int i=1; i<n; i++)
		for (int j=i+1; j<=n; j++)
		{
			double x1, y1, x2, y2, x3, y3;
			x1=x[j]-x[i];
			y1=y[j]-y[i];
			x2=x1*(1.0/2.0)-y1*(sqrt(3.0)/2.0)+x[i];
			y2=x1*(sqrt(3.0)/2.0)+y1*(1.0/2.0)+y[i];
			binar(x2, y2);
			x3=x1*(1.0/2.0)+y1*(sqrt(3.0)/2.0)+x[i];
			y3=y1*(1.0/2.0)-x1*(sqrt(3.0)/2.0)+y[i];
			binar(x3, y3);
		}
	fprintf(g, "%d", nr/3);
}

						

int main()
{
	read();
	quicksort(1, n);
	program();
	return 0;
}