Cod sursa(job #1682749)

Utilizator sucureiSucureiRobert sucurei Data 10 aprilie 2016 12:53:59
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

ifstream cin("triang.in");
ofstream cout("triang.out");

const double EPS = 0.001;

struct pct {
    double x, y;
};

pct p[1 + 1500];

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

int n;

bool verif(int l, double x, double y) {
    if (fabs(p[l].x - x) < EPS) {
        return p[l].y < y;
    } else {
        return p[l].x < x;
    }
}

bool cb(int l, double x, double y) {
    for (int pas = 1<<10; pas; pas /= 2) {
        if (l + pas <= n && verif(l + pas, x, y)) {
            l += pas;
        }
    }
    if ((fabs(p[l].x - x) < EPS && fabs(p[l].y - y) < EPS) || (n != l && fabs(p[l + 1].x - x) < EPS && fabs(p[l + 1].y - y) < EPS)) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    int i, j, rez = 0;
    cin>>n;
    for(i = 1; i <= n; ++i) {
        cin>>p[i].x>>p[i].y;
    }
    sort(p + 1, p + n + 1, cmp);
    double sin = sqrt(3) * 0.5;
    for(i = 1; i <= n - 2; ++ i) {
        for(j = i + 1; j <= n - 1; ++ j) {
            double CatX, CatY, MidX, MidY;
            CatX = p[j].x - p[i].x;
            CatY = p[j].y - p[i].y;
            CatY = -CatY;
            MidX = (p[i].x + p[j].x) * 0.5;
            MidY = (p[i].y + p[j].y) * 0.5;
            if (cb(j + 1, MidX + CatY * sin, MidY + CatX * sin)) {
                ++rez;
            }
            if (cb(j + 1, MidX - CatY * sin, MidY - CatX * sin)) {
                ++rez;
            }
        }
    }
    cout<<rez<<"\n";
    return 0;
}