Cod sursa(job #2466257)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 1 octombrie 2019 19:56:41
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#define DIM 1010
#define EPS 0.000001
using namespace std;

ifstream fin ("patrate3.in");
ofstream fout ("patrate3.out");
struct punct{
    double x,y;
};
punct v[DIM];
int n,i,j;
double modul (double x){
    if (x < 0)
        return -x;
    return x;
}
int cautare_binara (double x, double y){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (modul(x-v[mid].x) <= EPS && modul(y-v[mid].y) <= EPS)
            return 1; /// am gasit punctul
        if (x-v[mid].x >= EPS)
            st = mid+1;
        else {
            if (modul(x-v[mid].x) <= EPS && y-v[mid].y > EPS)
                st = mid+1;
            else dr = mid-1;
        }}
    return 0;
}
inline int cmp (punct a, punct b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;

    sort (v+1,v+n+1,cmp);
    int sol = 0;
    for (i=1;i<=n;i++){
        for (j=i+1;j<=n;j++){
            double x,x2,y,y2,xm,ym,dx,dy;
            xm = (v[i].x+v[j].x)/2.0, ym = (v[i].y+v[j].y)/2.0;
            dx = modul (v[i].x-xm), dy = modul(v[i].y-ym);
            if (v[i].y < v[j].y){
                x = xm + dy, y = ym - dx;
                x2 = xm - dy , y2 = ym + dx;
            } else {
                x = xm - dy, y = ym - dx;
                x2 = xm + dy , y2 = ym + dx;
            }
            if (cautare_binara(x,y) && cautare_binara(x2,y2)){
                sol++;
                //fout<<i<<" "<<j<<"\n";
            }}}
    fout<<sol/2;

    return 0;
}