Cod sursa(job #811311)

Utilizator Tester66Tester66 Tester66 Data 11 noiembrie 2012 21:42:34
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <cstdio>
#include <cstdlib>
#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(pd A)
{
    int left = 0, 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) left = mid + 1;
            else right = mid - 1;
        }else
        {
            if(A.f < V[mid].f) left = mid + 1;
            else right = 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()
{
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);
    int i, j;
    scanf("%i", &N);
    for(i = 1; i <= N; i++)
    {
        double X, Y;
        scanf("%lf %lf", &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(V[i].f == V[j].f)
            {
                now.f = V[i].f + L * sqrt(3) / 2;
                now.s = (V[i].s + V[j].s) / 2;
                if(BS(now))
                    ans ++;
                now.f = V[i].f - L * sqrt(3) / 2;
                now.s = (V[i].s + V[j].s) / 2;
                if(BS(now))
                    ans ++;
                continue;
            }
            if(V[i].s == V[j].s)
            {
                now.f = (V[i].f + V[j].f) / 2;
                now.s = V[i].s + L * sqrt(3) / 2;
                if(BS(now))
                    ans ++;
                now.f = (V[i].f + V[j].f) / 2;
                now.s = V[i].s - L * sqrt(3) / 2;
                if(BS(now))
                    ans ++;
                continue;
            }
            double a = 1;
            double b = -2 * ((V[i].f + V[j].f) / 2);
            double x0 = (V[i].f + V[j].f) / 2, y0 = (V[i].s + V[j].s) / 2;
            double m = (V[i].s - V[j].s) / (V[i].f - V[j].f);
            double c = x0 * x0 - 3 * L / (4 * (m * m + 1));
            double delt = b * b - 4 * a * c;
            now;
            now.f = (-b + sqrt(delt)) / 2.0;
            now.s = m * (now.f - x0) + y0;
            if(BS(now)) ans ++;
            now.f = (-b - sqrt(delt)) / 2.0;
            now.s = m * (now.f - x0) + y0;
            if(BS(now)) ans ++;
        }
    printf("%i\n", ans);
    return 0;
}