Cod sursa(job #2808498)

Utilizator hoprixVlad Opris hoprix Data 25 noiembrie 2021 11:01:36
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

const double error = 1e-3;
const double cos60 = 0.5;
const double sin60 = 0.8660254;

int n, k;

struct point {
    double x, y;
} p[1501];

bool cmp(point a, point b) {
    return a.x < b.x || (fabs(a.x - b.x) < error && a.y < b.y);
}

bool bsearch(int st, int dr, double tx, double ty) {
    while (st <= dr) {
        int mj = (st+dr)/2;
        if (fabs(tx-p[mj].x) < error && fabs(ty-p[mj].y) < error)
            return 1;
        if (p[mj].x < tx)
            st = mj+1;
        else
            dr = mj-1;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    fin >> n;
    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-1; i++)
        for (int j = i+1; j < n; j++) {
            double dx, dy, xx, yy;

            dx = p[j].x - p[i].x;
            dy = p[j].y - p[i].y;
            
            xx = dx*cos60 - dy*sin60 + p[i].x;
            yy = dy*cos60 + dx*sin60 + p[i].y;
            
            k += bsearch(j+1, n, xx, yy);
            
            xx = dx*cos60 + dy*sin60 + p[i].x;
            yy = dy*cos60 - dx*sin60 + p[i].y;

            k += bsearch(j+1, n, xx, yy);
        }
    fout << k;

    return 0;
}