Cod sursa(job #1200152)

Utilizator tudi98Cozma Tudor tudi98 Data 21 iunie 2014 23:23:01
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

#define pb push_back
#define PI 3.14159265
#define dim 1505

struct point{double x,y;};

point a[dim];

inline double atg(point a,point b){
	return (double)(a.y-b.y)/(a.x-b.x);
}

inline double dist(point a,point b){
	return (double)sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int search(int l,int r,double x,double y){
	if(l>r) return 0;
	int mid=(l+r)/2;
	if(fabs(a[mid].x-x)<0.001 && fabs(a[mid].y-y)<0.001)
		return mid;
	if(a[mid].x<x)
		return search(mid+1,r,x,y);
	return search(l,mid-1,x,y);
}

struct comp{
	bool operator()(const point &a,const point &b){
		if(a.x==b.x) return a.y < b.y;
		return a.x < b.x;
	}
};

int main(){

	ifstream f("triang.in");
	ofstream g("triang.out");

	int i,j,n,nr=0;
	f >> n;	
	for(i=0;i<n;i++){
		f >> a[i].x >> a[i].y;
	}
	sort(a,a+n,comp());	

	for(i=0;i<n-2;i++){
		for(j=i+1;j<n-1;j++){
			point mid;
			mid.x=(double)fabs(a[i].x-a[j].x)/2+a[i].x;
			mid.y=(double)fabs(a[i].y-a[j].y)/2+min(a[i].y,a[j].y);
			double alfa=atg(a[i],a[j]);
			double phi=-(1/alfa);
			double l=dist(a[i],a[j]);
			double h=l*sqrt(3)/2; 
			double k=h*h/(phi*phi+1);
			if(search(j+1,n-1,mid.x+sqrt(k),phi*sqrt(k)+mid.y)!=0) nr++;
			if(search(j+1,n-1,mid.x-sqrt(k),mid.y-phi*sqrt(k))!=0) nr++;
		     /* g << "x1 = " << a[i].x << ";   y1= " << a[i].y <<"\n";
			g << "x2 = "<< a[j].x <<";   y2= "<< a[j].y <<"\n";
			g << "xmid = " << mid.x <<";   ymid= " << mid.y <<"\n";
			g << "alfa = " << alfa <<"\n";
			g << "phi = " << phi <<"\n";
			g << "k = " << k <<"\n";
			g << "l = " << l <<"\n"; 
			g << "h = " << h <<"\n";
			g << "x12 = " << mid.x+sqrt(k) <<"   " <<mid.x-sqrt(k) <<"\n";
			g << "y12 = " << mid.y+phi*sqrt(k) <<"   "<<mid.y-phi*sqrt(k) << "\n";
		     */
		}
	}
	g << nr;
}