Cod sursa(job #2890942)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 17 aprilie 2022 00:22:25
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 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 x < a.x || (x == a.x && y < a.y);
    }

};


point v[1501];
int n, ans;
set<point> s;

double dist(point a, point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

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;
        if (abs(v[mij].x - m.x) < 0.001) {
            while (l <= r) {
                 int mij = (l + r) >> 1;
                 if (abs(v[mij].y - m.y) < 0.001)
                    return 1;
                 if (v[mij].y < m.y)
                        l = mij + 1;
                 else
                        r = mij - 1;
            }
            return 0;
        }
        if (v[mij].x < m.x)
            l = mij + 1;
        else
            r = mij - 1;
    }
    return 0;
}

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

    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            double d = dist(v[i], v[j]);
            int lans = ans;
            point mid;
            mid.x = (v[i].x + v[j].x) * 0.5;
            mid.y = (v[i].y + v[j].y) * 0.5;
            double h = (sqrt(3) * d) * 0.5;
            point src;

            src.x = mid.x + h;
            src.y = mid.y + h;

            if (Find(v, src)) {
                ans++;
            }


            src.x = mid.x - h;
            src.y = mid.y + h;
            if (Find(v, src)) {
                ans++;
            }


            src.x = mid.x + h;
            src.y = mid.y - h;
            if (Find(v, src)) {
                ans++;
            }


            src.x = mid.x - h;
            src.y = mid.y - h;
            if (Find(v, src)) {
                ans++;
            }


            src.x = mid.x - h;
            src.y = mid.y;
            if (Find(v, src)) {
                ans++;
            }


            src.x = mid.x + h;
            src.y = mid.y;
            if (Find(v, src)) {
                ans++;
            }


            src.y = mid.y - h;
            src.x = mid.x;
            if (Find(v, src)) {
                ans++;
            }


            src.y = mid.y + h;
            src.x = mid.x;
            if (Find(v, src)) {
                ans++;
            }

        }

    out<<ans;
}