Cod sursa(job #2157382)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 9 martie 2018 16:27:41
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <bits/stdc++.h>

using namespace std;

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

const double EPS = 1e-8;

struct Point{
    double x,y;
}A[1010];

int N;


inline bool isEqual(const double &a, const double &b){
    return abs(a - b) < EPS;
}

inline bool pEqual(const Point &a,const Point &b){
    return isEqual(a.x,b.x) && isEqual(a.y,b.y);
}

bool comp(const Point &a,const Point &b){
    if (isEqual(a.x,b.x)) return a.y < b.y;
    return a.x < b.x;
}

bool binSearch(Point B){
    int left = 1, right = N;
    while (left <= right){
        int mid = (left + right) / 2;
        if (pEqual(A[mid],B)) return 1;
        if (isEqual(A[mid].x,B.x)){
            if (A[mid].y < B.y) left = mid + 1;
            else right = mid - 1;
        }else{
            if (A[mid].x < B.x) left = mid + 1;
            else right = mid - 1;
        }

    }
    return 0;
}

int main(){
    fin >> N;
    for (int i = 1; i <= N;i++) fin >> A[i].x >> A[i].y;
    sort(A + 1, A + N + 1,comp);
    //cout <<binSearch(A[1]);
    int ans = 0;
    for (int i = 1; i < N;i++){
        for (int j = i + 1; j <= N;j++){
            Point A1,B,M;
            M.x = (1.0*A[i].x + A[j].x)/2;
            M.y = (1.0*A[i].y + A[j].y)/2;

            A1.x = M.x - (1.0*A[j].y - M.y);
            A1.y = M.y + (1.0*A[j].x - M.x);

            B.x = M.x + (1.0*A[j].y - M.y);
            B.y = M.y - (1.0*A[j].x - M.x);
            //cout << A1.x << " " << A1.y << " " << B.x << " " << B.y << endl;
            //cout <<  binSearch(A1) << binSearch(B)<<endl;
            ans += binSearch(A1) && binSearch(B);
        }
    }
    cout << ans;
    return 0;
}