Cod sursa(job #2307300)

Utilizator mihaicivMihai Vlad mihaiciv Data 24 decembrie 2018 11:37:45
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("patrate3.in");
ofstream g("patrate3.out");
struct point {
    double x, y;
}pointsArray[1111];
int n;
double eps = 0.0001;

bool cmp(point A, point B) {
    if (A.x < B.x) {
        return true;
    } else if (A.x == B.x && A.y < B.y) {
        return true;
    }
    return false;
}

int isHigherPoint(point p1, point p2) {
    if (abs(p1.x - p2.x) <= eps) {
        if (abs(p1.y - p2.y) <= eps) {
            return 0;
        } else {
            if (p1.y > p2.y) { return -1; }
            else { return 1; }
        }
    } else {
        if (p1.x > p2.x) {
            return -1;
        } else {
            return 1;
        }
    }
}

bool findPoint(int left, int right, point P) {
    if (left == right) {
        if ( isHigherPoint(P, pointsArray[left]) == 0 ) {
            return true;
        } else {return false;}
    } else {
        int mid = (left + right) / 2;
        if ( isHigherPoint(P, pointsArray[mid]) == -1 ) {
            return findPoint(mid + 1, right, P);
        } else {
            return findPoint(left, mid, P);
        }
    }
}

int main() {

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

    sort(pointsArray, pointsArray + n, cmp);
    int answer = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            point mid;
            mid.x = (pointsArray[i].x + pointsArray[j].x) / 2.0;
            mid.y = (pointsArray[i].y + pointsArray[j].y) / 2.0;

            double dx = abs(pointsArray[i].x - mid.x);
            double dy = abs(pointsArray[i].y - mid.y);
            point p3, p4; // celelalte 2 puncte
            if (pointsArray[i].y < pointsArray[j].y) {
                p3.x = mid.x + dy;
                p3.y = mid.y - dx;
                p4.x = mid.x - dy;
                p4.y = mid.y + dx;


            } else {
                p3.x = mid.x - dy;
                p3.y = mid.y - dx;
                p4.x = mid.x + dy;
                p4.y = mid.y + dx;
            }

            if ( findPoint(0, n - 1, p3) && findPoint(0, n - 1, p4) ) {
                answer ++;
            }

        }
    }

    g << answer / 2;

    return 0;
}