Cod sursa(job #2890947)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 17 aprilie 2022 02:56:10
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("triang.in");
ofstream out("triang.out");

struct point
{
    long double x, y;

};

const long double eps = 0.001;
bool cmp(point a, point b)
{
    return (a.x < b.x || (abs(a.x - b.x) < eps && a.y < b.y));
}

point v[1501];
int n, ans;

bool Find(point v[], point m)
{
    //cout<<m.x<<" "<<m.y<<'\n';
    int l = 1, r = n;
    while (l <= r) {
        int mij = (l + r) >> 1;
        //cout<<mij<<'\n';
        if (fabs(v[mij].x - m.x) < eps && fabs(v[mij].y - m.y) < eps)
            return 1;
        if (v[mij].x > m.x || (fabs(v[mij].x - m.x) < eps && v[mij].y > m.y))
            r = mij - 1;
        else
            l = mij + 1;
    }
    //cout<<'\n';
    return 0;
}

int main()
{
    in>>n;
    for (int i = 1; i <= n; i++) {
        in>>v[i].x>>v[i].y;
    }
    sort(v + 1, v + n + 1, cmp);

    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {

            point src;

            src.x = (v[i].x * 0.5 + v[j].x * 0.5 + sqrt(3) * 0.5 * (v[i].y - v[j].y));
            src.y = (v[i].y * 0.5 + v[j].y * 0.5 + sqrt(3) * 0.5 * (v[j].x - v[i].x));
            //cout<<v[i].x<<" "<<v[i].y<<'\n'<<v[j].x<<" "<<v[j].y<<'\n'<<" "<<src.x<<" "<<src.y<<'\n';
            if (Find(v, src))
                ans++;

            src.x = (v[i].x * 0.5 + v[j].x * 0.5 - sqrt(3) * 0.5 * (v[i].y - v[j].y));
            src.y = (v[i].y * 0.5 + v[j].y * 0.5 - sqrt(3) * 0.5 * (v[j].x - v[i].x));
            //cout<<v[i].x<<" "<<v[i].y<<'\n'<<v[j].x<<" "<<v[j].y<<'\n'<<" "<<src.x<<" "<<src.y<<'\n';
            if (Find(v, src))
                ans++;
        }

    out<<ans / 3;
}