Cod sursa(job #811367)

Utilizator visanrVisan Radu visanr Data 11 noiembrie 2012 23:22:43
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

#define eps 1e-3
#define nmax 1510
#define pd pair<double, double>
#define pb push_back
#define mp make_pair
#define f first
#define s second

int N;
vector<pd> V;
pd now;


double dist(pd A, pd B)
{
    return sqrt((A.f - B.f) * (A.f - B.f) + (A.s - B.s) * (A.s - B.s));
}

bool BS(int start, pd A)
{
    int left = start, right = N - 1, mid;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(fabs(A.f - V[mid].f) < eps)
        {
            if(fabs(A.s - V[mid].s) < eps)
                return 1;
            if(A.s < V[mid].s) right = mid - 1;
            else left = mid + 1;
        }else
        {
            if(A.f < V[mid].f) right = mid - 1;
            else left = mid + 1;
        }
    }
    return 0;
}

bool cmp(pd A, pd B)
{
    if(fabs(A.f - B.f) < eps) return A.s < B.s;
    else return A.f < B.f;
}

int main()
{
    ifstream in("triang.in");
    ofstream out("triang.out");
    int i, j;
    in >> N;
    for(i = 1; i <= N; i++)
    {
        double X, Y;
        in >> X >> Y;
        V.pb(mp(X, Y));
    }
    sort(V.begin(), V.end(), cmp);
    int ans = 0;
    for(i = 0; i < N; i++)
        for(j = i + 1; j < N; j++)
        {
            double L = dist(V[i], V[j]);
            if(fabs(V[i].f - V[j].f) < eps)
            {
                now.f = V[i].f + L * sqrt(3.0) / 2.0;
                now.s = (V[i].s + V[j].s) / 2.0;
                if(BS(j + 1, now))
                    ans ++;
                now.f = V[i].f - L * sqrt(3.0) / 2.0;
                now.s = (V[i].s + V[j].s) / 2.0;
                if(BS(j + 1, now))
                    ans ++;
                continue;
            }
            if(fabs(V[i].s - V[j].s) < eps)
            {
                now.f = (V[i].f + V[j].f) / 2.0;
                now.s = V[i].s + L * sqrt(3.0) / 2.0;
                if(BS(j + 1, now))
                    ans ++;
                now.f = (V[i].f + V[j].f) / 2.0;
                now.s = V[i].s - L * sqrt(3.0) / 2.0;
                if(BS(j + 1, now))
                    ans ++;
                continue;
            }
            double x0 = (V[i].f + V[j].f) / 2.0, y0 = (V[i].s + V[j].s) / 2.0;
            double m = (V[i].s - V[j].s) / (V[i].f - V[j].f);
            m = (-1.0) / m;
            double c = x0 * x0 - 3.0 * L * L / (4.0 * (m * m + 1.0));
            double delt = sqrt(4 * x0 * x0 - 4.0 * c) / 2;
            now.f = x0 + delt;
            now.s = m * (now.f - x0) + y0;
            if(BS(j + 1, now)) ans ++;
            now.f = x0 - delt;
            now.s = m * (now.f - x0) + y0;
            if(BS(j + 1, now)) ans ++;
        }
    out << ans;
    return 0;
}