Cod sursa(job #2890946)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 17 aprilie 2022 01:55:50
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>

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

struct point
{
    double x, y;
    bool operator < (const point& a) const{
            return y < a.y || (y == a.y && x < a.x);
    }

};


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 (abs(v[mij].x - m.x) < 0.001 && abs(v[mij].y - m.y) < 0.001)
            return 1;
        if (abs(v[mij].x - m.x) < 0.001 || abs(v[mij].y - m.y) < 0.001)
            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);

    for (int i = n; i > 0; i--)
        for (int j = i - 1; j > 0; j--) {

            point src;

            src.x = (v[i].x + v[j].x + sqrt(3) * (v[i].y - v[j].y)) * 0.5;
            src.y = (v[i].y + v[j].y + sqrt(3) * (v[j].x - v[i].x)) * 0.5;
            //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 + v[j].x - sqrt(3) * (v[i].y - v[j].y)) * 0.5;
            src.y = (v[i].y + v[j].y - sqrt(3) * (v[j].x - v[i].x)) * 0.5;
            //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;
}