Cod sursa(job #1959343)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 9 aprilie 2017 13:21:18
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
#define MOD 10007
#define sinus 0.86602540378443864676372317075294
#define eps 0.001
using namespace std;
  
FILE*IN,*OUT;

double x,y;
struct complex
{
	double r,i;
	void operator -=(complex &a)
	{
		r-=a.r;
		i-=a.i;
	}
	void operator +=(complex &a)
	{
		r+=a.r;
		i+=a.i;
	}
	void operator *=(complex &a)
	{
		double ra=r*a.r-i*a.i;
		double ia=r*a.i+i*a.r;
		r=ra,i=ia;
	}
	bool operator <(complex &a)const
	{
		return r-a.r<-eps||(abs(r-a.r)<=eps&&i-a.i<-eps);
	}
	bool operator >(complex &a)const
	{
		return r-a.r>eps||(abs(r-a.r)<=eps&&i-a.i>eps);
	}
}v[MaxN],aux;
complex Rotate(complex point,complex origin)
{
	point-=origin;
	complex R={0.5,sinus};
	point*=R;
	point+=origin;
	return point;
}
int N,cnt=0;
vector<complex> H[MOD];
bool cond(complex a,complex b)
{
	return a.r-b.r<0||(abs(a.r-b.r)<=eps&&a.i-b.i<-eps);
}
bool Search(complex a)
{
	int lw=1,hi=N,mid;
	while(lw<=hi)
	{
		mid=(lw+hi)>>1;
		if(a<v[mid])
			hi=mid-1;
		else if(a>v[mid])
			lw=mid+1;
		else return true;
	}
	return false;
}
int main()
{
    IN=fopen("triang.in","r");
    OUT=fopen("triang.out","w");
	
	fscanf(IN,"%d",&N);
	for(int i=1;i<=N;i++)
		fscanf(IN,"%lf%lf",&v[i].r,&v[i].i);
	sort(v+1,v+1+N,cond);
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
		{
			aux=Rotate(v[j],v[i]);
			if(Search(aux))
				cnt++;
		}
	fprintf(OUT,"%d",cnt);
    return 0;
}