Cod sursa(job #1959340)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 9 aprilie 2017 13:16:58
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
#define MOD 10007
#define alpha 1.0471975511965977461542144610932
#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,long double angle)
{
	point-=origin;
	complex R={cos(angle),sin(angle)};
	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<0);
}
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],alpha);
			if(Search(aux))
				cnt++;
			aux=Rotate(v[j],v[i],-alpha);
			if(Search(aux))
				cnt++;
		}
	fprintf(OUT,"%d",cnt/3);
    return 0;
}