Cod sursa(job #1937434)

Utilizator raluca1234Tudor Raluca raluca1234 Data 23 martie 2017 22:54:46
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define maxN 1000
#define EPS

using namespace std;

int N;
struct POINT{
    int x, y;
}v[maxN+1];

inline bool cmp(POINT A, POINT B){
    if (A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}

inline bool binarySearch(POINT P){
    int left, right, mid;
    left=1;
    right=N;
    while (left<=right){
        mid=(left+right)/2;
        if (v[mid].x==P.x && v[mid].y==P.y)
            return true;
        if (v[mid].x<P.x || (v[mid].x==P.x && v[mid].y<P.y))
            left=mid+1;
        else
            right=mid-1;
    }
    return false;
}

int main(){
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);

    scanf("%d", &N);

    for (int i=1; i<=N; i++){
        double xi, yi;
        scanf("%lf%lf", &xi, &yi);
        v[i].x=round(xi*10000);
        v[i].y=round(yi*10000);
    }
    sort(v+1, v+N+1, cmp);

    int ans=0;
    for (int i=1; i<=N; i++)
        for (int j=i+1; j<=N; j++){
            POINT mid;
            mid.x=(v[i].x+v[j].x)/2;
            mid.y=(v[i].y+v[j].y)/2;

            int dx, dy;
            dx=abs(mid.x-v[i].x);
            dy=abs(mid.y-v[i].y);

            POINT P1, P2;
            if (v[i].y<v[j].y){
                P1.x=mid.x+dy;
                P1.y=mid.y-dx;
                P2.x=mid.x-dy;
                P2.y=mid.y+dx;
            }else{
                P1.x=mid.x-dy;
                P1.y=mid.y-dx;
                P2.x=mid.x+dy;
                P2.y=mid.y+dx;
            }

            if (binarySearch(P1) && binarySearch(P2)){
                ans++;
            }
        }

    printf("%d\n", ans/2);
    return 0;
}