Cod sursa(job #1021049)

Utilizator enedumitruene dumitru enedumitru Data 3 noiembrie 2013 08:31:49
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream f ("triang.in"); ofstream g ("triang.out");
struct punct {double x,y;} a[1501];
double eps = 0.001;
double si=1.7320508/2, co=0.5;
int n,i,j,sol;
inline double abss (double a) {return a<0 ? a*-1.0 : a;}
inline bool egal(double a, double b) {return abss(a-b)<eps;}
inline bool mic(double a, double b) {return a-b<eps;}
inline bool cmp (punct a, punct b)
{	if(egal(a.x,b.x)) return mic(a.y,b.y);
    return mic(a.x,b.x);
}
inline punct p1(punct a, punct b)
{   punct c;
    c.x=a.x+(b.x-a.x)*co-(b.y-a.y)*si;
    c.y=a.y+(b.x-a.x)*si+(b.y-a.y)*co;
    return c;
}
inline punct p2 (punct a, punct b)
{   punct c;
    c.x=a.x+(b.x-a.x)*co+(b.y-a.y)*si;
    c.y=a.y-(b.x-a.x)*si+(b.y-a.y)*co;
    return c;
}
inline int bs (punct c, int j)
{   int i,cnt=(1<<11);
    for(i=j; cnt; cnt>>=1)
	{   int aux=i+cnt;
        if(aux<=n)
         if(mic(a[aux].x,c.x) || (egal(a[aux].x,c.x) && mic(a[aux].y,c.y))) i=aux;
    }
	return (egal(c.x,a[i].x) && egal(c.y,a[i].y) ? 1 : 0);
}
int main ()
{   f>>n;
    for(i=1; i<=n; ++i)
        f>>a[i].x>>a[i].y;
    sort (a+1,a+n+1,cmp);
    for(i=1; i<n-1; ++i)
        for (j=i+1; j<n; ++j)
        {   if(bs(p1(a[i],a[j]),j+1)) ++sol;
            if(bs(p2(a[i],a[j]),j+1)) ++sol;
        }
    g<<sol<<'\n'; g.close (); return 0;
}