Cod sursa(job #1197760)

Utilizator dalv_1337Pasita Vlad dalv_1337 Data 13 iunie 2014 18:07:25
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int nMax = 1501;
const double eps = 0.001;

struct coord{ double x, y; } v[nMax];
struct{ double x, y; } C1, C2;

inline bool cmp(coord a,coord b)
{	return a.x<b.x || (a.x==b.x && a.y<b.y);   }

inline void calcul(double x1,double y1,double x2,double y2)
{
	double p, l, xm, ym, a, b, c, delta;
	
	p = (x1-x2)/(y2-y1); // panta dreptei AB
	l = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1); // lungimea laturii triunghiului ABC ^2
	xm = (x1+x2)/2; // abscisa punctului de intersectie dintre AB si CD
	ym = (y1+y2)/2; // ordonata punctului de intersectie dintre AB si CD
	// a*x^2 + b*x + c = 0
	a = p*p + 1;
	b = -2*p*p*xm + 2*p*ym - 2*p*y1 - 2*x1;
	c = p*p*xm*xm - 2*p*xm*ym + 2*p*xm*y1 + x1*x1 + ym*ym - 2*ym*y1 + y1*y1 - l;

	delta = b*b - 4*a*c;
	C1.x = (-b+sqrt(delta))/(2*a);
	C2.x = (-b-sqrt(delta))/(2*a);
	// ecuatia dreptei CD: y-ym = p*(x-xm) => y = p*(x-xm)+ym
	C1.y = p*(C1.x-xm)+ym;
	C2.y = p*(C2.x-xm)+ym;
}

inline bool bin_search(int st,int dr,double x,double y)
{
	int mij;
	while (st<=dr) {
		mij=(st+dr)>>1;
		if (fabs(x-v[mij].x)<eps && fabs(y-v[mij].y)<eps) return true;
		if (v[mij].x<x || (fabs(x-v[mij].x)<eps && v[mij].y<y)) st=mij+1;
		else dr=mij-1;
	}
	return false;
}

int main()
{
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	
	int n;
	scanf("%d",&n);
	for (int i=1; i<=n; ++i) scanf("%lf%lf",&v[i].x,&v[i].y);
	
	sort(v+1,v+n+1,cmp);
	
	int sol=0;
	for (int j,i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j) {
			calcul(v[i].x,v[i].y,v[j].x,v[j].y); // A(x1,y1), B(x2,y2), mu(CD,AB)=90deg -> C(x3,y3)
			if (bin_search(j+1,n,C1.x,C1.y)) ++sol;
			if (bin_search(j+1,n,C2.x,C2.y)) ++sol;
		}

	printf("%d",sol);
	
	return 0;
}