Cod sursa(job #3234596)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 10 iunie 2024 13:43:44
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;

ifstream f ("triang.in");
ofstream g ("triang.out");

const int NMAX = 15e2;
const double EPS = 1e-3;
int n, sol;

struct punct {
    double x, y;
};

punct P[NMAX+1];

bool cmp(const punct &a, const punct &b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

bool cautbin(punct X) {
    int p=1, u=n;
    while (p<=u) {
        int m = (p+u)/2;
        if  (abs(P[m].x - X.x) <= EPS)
            if (abs(P[m].y - X.y) <= EPS)
                return 1;
            else if (P[m].y < X.y)
                p = m+1;
            else
                u = m-1;
        else if (P[m].x < X.x)
            p = m+1;
        else
            u = m-1;
    }
    return 0;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; i++)
        f >> 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++) {
            punct A = P[i], B = P[j], C, M;
            M.x = (A.x+B.x)/2;
            M.y = (A.y+B.y)/2;
            //
            C.x = M.x - sqrt(3) * (A.y - M.y);
            C.y = M.y + sqrt(3) * (A.x - M.x);
            if (cautbin(C))
                sol++;
            //
            C.x = M.x + sqrt(3) * (A.y - M.y);
            C.y = M.y - sqrt(3) * (A.x - M.x);
            if (cautbin(C))
                sol++;
        }
    }
    g << sol / 3;
    f.close();
    g.close();
    return 0;
}