Cod sursa(job #1096158)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 1 februarie 2014 16:51:22
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

ifstream fin("triang.in");
ofstream fout("triang.out");

const int Nmax = 1550;
const double EPS = 1e-7;
const double sin60 = sin(M_PI / 3.00);
const double cos60 = cos(M_PI / 3.00);

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

int N, LG, sol;

bool cmp(const pct &a, const pct &b)
{
    if(fabs(a.x - b.x) < EPS)
    {
        if(fabs(a.y - b.y) < EPS) return 0;
        return a.y < b.y;
    }
    return a.x < b.x;
}

pct TVarf(pct a, pct b)
{
    pct c;
    double dx = b.x - a.x, dy = b.y - a.y;
    c.x = a.x + dx * cos60 - dy * sin60;
    c.y = a.y + dx * sin60 + dy * cos60;
    return c;
}

int Egal(pct a, pct 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;
}
 bool CB(pct 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;

}

int main()
{
    fin >> N;
    for(LG = 1; LG <= N; LG <<= 1);

    for(int i = 1; i <= N; i++)
        fin >> P[i].x >> P[i].y;

    sort(P + 1, P + N + 1, cmp);

    for(int i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++)
        {
            pct A = TVarf(P[i], P[j]), B = TVarf(P[j], P[i]);
            if(CB(A)) sol++;
            if(CB(B)) sol++;
        }
    fout << sol / 3;
    return 0;
}