Cod sursa(job #2314855)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 9 ianuarie 2019 04:04:19
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define N 1024
#define f first
#define s second
pair<double,double> v[N],m,variatie,colturi[2];
int i,j,n,ans;
const double prag = 0.00001;
double modul (double x){
    if (x > 0)
        return x;
    return -x;
}
int egalitate (double a,double b){
    if(modul(a - b) < prag)
        return 1;
    return 0;
}
int before (pair<double,double> a, pair<double,double> b){
    if (egalitate (a.f,b.f))
        return (a.s < b.s);
    return (a.f < b.f);
}
int bs (pair<double,double> a){
    int p = 0;
    for (int i = n - 1; i > 0; i >>= 1)
        while (i + p < n && before(v[i + p],a))
        p += i;
    if (egalitate (a.f,v[p + 1].f) && egalitate (a.s,v[p + 1].s))
        return 1;
    if (egalitate (a.f,v[p].f) && egalitate (a.s,v[p].s))
        return 1;
    return 0;
}
int main()
{
    ifstream fin ("patrate3.in");
    fin >> n;
    for (i = 0; i < n; ++i)
        fin >> v[i].f >> v[i].s;
    sort(v,v + n);
    ans = 0;
    for (i = 0; i < n; ++i)
    for (j = i + 1 ; j < n; ++j){
        m.f = (v[i].f + v[j].f) / 2;
        m.s = (v[i].s + v[j].s) / 2;
        variatie.f = modul(v[i].f - m.f);
        variatie.s = modul(v[i].s - m.s);
        if (v[i].s < v[j].s){
            colturi[0].f = m.f + variatie.s;
            colturi[0].s = m.s - variatie.f;
            colturi[1].f = m.f - variatie.s;
            colturi[1].s = m.s + variatie.f;
        }
        else{
            colturi[0].f = m.f - variatie.s;
            colturi[0].s = m.s - variatie.f;
            colturi[1].f = m.f + variatie.s;
            colturi[1].s = m.s + variatie.f;
        }
        if (bs(colturi[0]) && bs(colturi[1]))
            ++ans;
    }
    ofstream fout ("patrate3.out");
    fout << ans / 2;
    return 0;
}