Cod sursa(job #1070636)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 1 ianuarie 2014 18:31:20
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <algorithm>
#define Nmax 1505
#define eps 0.00000001
#define sin60 0.8660254037844

using namespace std;

int N;

struct coord
{
    double x,y;
};
coord v[Nmax],C;

inline void Read()
{
    ifstream fin("triang.in");
    fin>>N;
    for(int i=1;i<=N;++i)
        fin>>v[i].x>>v[i].y;
    fin.close();
}

inline bool cmp(const coord A, const coord B)
{
    return (A.x<B.x || (A.x==B.x && A.y<B.y));
}

inline int Compara(coord A, coord B)
{
    if(A.x-B.x<eps)
    {
        if(A.y-B.y<eps)
            return 0;
        else
            if(A.y>B.y)
                return 1;
            else
                return -1;
    }
    if(A.x>B.x)
        return 1;
    else
        return -1;
}

inline int BSearch(coord A)
{
    int st=1,dr=N,mij,ok;
    coord B;
    while(st<=dr)
    {
        mij=((st+dr)>>1);
        B.x=v[mij].x; B.y=v[mij].y;
        ok=Compara(B,A);
        if(!ok)
            return 1;
        if(ok<0)
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}

int main()
{
    int i,j;
    coord A,B;
    long long sol=0;
    Read();
    sort(v+1,v+N+1,cmp);
    for(i=1;i<N;++i)
        for(j=i+1;j<=N;++j)
        {
            A.x=v[i].x; A.y=v[i].y;
            B.x=v[j].x; B.y=v[j].y;
            C.x=A.x + (B.x-A.x)/2 - sin60*(B.y-A.y);
            C.y=A.y + (B.y-A.y)/2 + sin60*(B.x-A.x);
            sol+=BSearch(C);

            C.x=A.x + (B.x-A.x)/2 + sin60*(B.y-A.y);
            C.y=A.y - (B.y-A.y)/2 + sin60*(B.x-A.x);
            sol+=BSearch(C);
        }
    sol/=3LL;
    ofstream fout("triang.out");
    fout<<sol<<"\n";
    fout.close();
    return 0;
}