Cod sursa(job #2890884)

Utilizator mihnea.tTudor Mihnea mihnea.t Data 16 aprilie 2022 21:33:39
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <bits/stdc++.h>

#define INF ((long long)1e9)
#define EPS ((double)1e-3)

using namespace std;

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

struct coord {
    double x, y;

    bool equalTo(const coord &other) {
        if (abs(this->x - other.x) < EPS && abs(this->y - other.y) < EPS) {
            return true;
        }

        return false;
    }

    bool smallerThan(const coord &other) {
        if (abs(this->x - other.x) < EPS) {
            return this->y < other.y;
        }

        return this->x < other.x;
    }
};

int n;
vector<coord> v;

void read_input() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        double x, y;
        fin >> x >> y;
        v.push_back({x, y});
    }
}

int find_point(coord &C) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (v[mid].equalTo(C)) {
            return mid;
        } else if (v[mid].smallerThan(C)) {
            left = mid + 1; 
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int check_triangle(int A_index, int B_index) {
    // Calculate the two C's
    // cout << A.x << " " << A.y << "\n";
    // cout << B.x << " " << B.y << "\n";

    coord A = v[A_index];
    coord B = v[B_index];

    coord C1 = {
        (A.x + B.x + sqrt(3) * (A.y - B.y)) / 2,
        (A.y + B.y + sqrt(3) * (B.x - A.x)) / 2
    };
    
    coord C2 = {
        (A.x + B.x - sqrt(3) * (A.y - B.y)) / 2,
        (A.y + B.y - sqrt(3) * (B.x - A.x)) / 2
    };

    int cnt = 0;
    int pos_C1 = find_point(C1);
    if (pos_C1 != -1) {
        ++cnt;
    }

    int pos_C2 = find_point(C2);
    if (pos_C2 != -1) {
        ++cnt;
    }

    // cout << fixed << setprecision(6) << x1 << " " << y1 << "\n";
    // cout << fixed << setprecision(6) << x2 << " " << y2 << "\n\n";

    return cnt;
}

int main(void) {
    read_input();

    sort(v.begin(), v.end(), [](coord &a, coord &b) {
        if (abs(a.x - b.x) > EPS) {
            return a.x < b.x;
        }

        return a.y < b.y;
    });

    // for (int i = 0; i < n; ++i) {
    //     cout << v[i].x << " " << v[i].y << "\n";
    // }

    int triang_cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            triang_cnt += check_triangle(i, j);
        }
    }

    fout << triang_cnt / 3 << "\n";

    fin.close();
    fout.close();

    return 0;
}