Cod sursa(job #1006578)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 7 octombrie 2013 12:59:46
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define Nmax 1599
#define eps 0.001
const double Cos60=1.0*cos(M_PI/3.0);
const double Sin60=1.0*sin(M_PI/3.0);
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");

int n,sol;
double d[Nmax][Nmax];

struct punct {double x,y;}P[Nmax];

bool cmp(punct a, punct b)
{
    if(fabs(a.x-b.x)<1e-5)
    {
        if(fabs(a.y-b.y)<1e-5) return 0;
        return a.y<b.y;
    }
    return a.x<b.x;
}
inline void ReadInput()
{
    f>>n;
    for(int i=1;i<=n;i++)f>>P[i].x>>P[i].y;

}



inline punct Varf(punct A,punct B)
{
    //se dau doua varfuri ale unui triunghi echilateral
    // punctul C este solutie pentru al treilea
    //sunt doua solutii diferite simetrice fata de mijlocul lui AB
    punct C;
    C.x=A.x+Cos60*(B.x-A.x)-Sin60*(B.y-A.y);
    C.y=A.y+Sin60*(B.x-A.x)+Cos60*(B.y-A.y);
    return C;
}

int Egal(punct a, punct b)
{
    if(fabs(a.x-b.x)<1e-5)
    {
        if(fabs(a.y-b.y)<1e-5) return 0;
        if(a.y>b.y)return 1;
        else return 2;
    }
    if(a.x>b.x)return 1;
    else return 2;
}
inline bool Exista(punct A)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int middle=(st+dr)/2;
        int ok=Egal(P[middle],A);
        if(!ok)return 1;
        else if(ok==1)dr=middle-1;
        else if(ok==2)st=middle+1;
    }
    return 0;

}
void Solve()
{
    sort(P+1,P+1+n,cmp);
    for(int i=1;i<=n-1;i++)
        for(int j=i+1;j<=n;j++)
            {
                punct X=Varf(P[i],P[j]),Y=Varf(P[j],P[i]);
                if(Exista(X))sol++;
                if(Exista(Y))sol++;
            }
    sol/=3;
    g<<sol<<'\n';
}

int main()
{
    ReadInput();
    Solve();
    f.close();g.close();
    return 0;
}