Cod sursa(job #3200864)

Utilizator not_anduAndu Scheusan not_andu Data 5 februarie 2024 22:14:29
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("03")

using namespace std;

#define INFILE "triang.in"
#define OUTFILE "triang.out"

typedef long double ld;

const ld EPS = 0.0001;

struct Point {

    ld x;
    ld y;

    Point() : x(0), y(0) {}
    Point(ld _x, ld _y) : x(_x), y(_y) {}

    bool operator<(const Point& other) const {
        return (this -> x < other.x || fabs(other.x - this -> x) < EPS && this -> y < other.y);
    }

};

int n;
vector<Point> v;

bool compare(Point &a, Point &b){
    return (a.x < b.x || fabs(b.y - a.x) < EPS && a.y < b.y);
}

void solve(){

    cin >> n;
    v.resize(n);

    for(int i = 0; i < n; ++i){
        cin >> v[i].x >> v[i].y;
    }

    sort(v.begin(), v.end());

    int ans = 0;

    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(i != j){
                
                Point aux;
                aux.x = (v[i].x + v[j].x + sqrt(3) * (v[i].y - v[j].y)) / 2;
                aux.y = (v[i].y + v[j].y + sqrt(3) * (v[j].x - v[i].x)) / 2;

                int left = j + 1, right = n - 1;
                bool found = false;
                while(left <= right && !found){
                    int middle = (left + right) >> 1;
                    if(fabs(v[middle].x - aux.x) < EPS && fabs(v[middle].y - aux.y) < EPS){
                        ++ans;
                    }
                    else if(compare(aux, v[middle])) right = middle - 1;
                    else left = middle + 1;
                }

                aux.x = (v[i].x + v[j].x - sqrt(3) * (v[i].y - v[j].y)) / 2.0;
                aux.y = (v[i].y + v[j].y - sqrt(3) * (v[j].x - v[i].x)) / 2.0;

                left = j + 1, right = n - 1;
                found = false;

                while(left <= right && !found){
                    int middle = (left + right) >> 1;
                    if(fabs(v[middle].x - aux.x) < EPS && fabs(v[middle].y - aux.y) < EPS){
                        ++ans, found = true;
                    }
                    else if(compare(aux, v[middle])) right = middle - 1;
                    else left = middle + 1;
                }
                
            }
        }
    }

    cout << ans << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}