Cod sursa(job #799089)

Utilizator vendettaSalajan Razvan vendetta Data 17 octombrie 2012 21:50:00
Problema Patrate 3 Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <cmath>

using namespace std;

ifstream f("patrate3.in");
ofstream g("patrate3.out");

#define nmax 1005
#define ll long long
#define X first
#define Y second
#define Eps 0.00001

int n;
pair<double, double> v[nmax];

void citeste(){

	f >> n;
	for(int i=1; i<=n; ++i){
        double x, y;
        f >> x >> y;
        v[i] = make_pair(x, y);
	}

    sort(v+1, v+n+1);

}

double modul(double X){

    if (X < 0.00000){
        X = X * -1.0000;
    }

    return X;

}

int cb(pair<double, double> x){

    int st = 0;
    int dr = n+1;
    while(dr - st > 1){
        int mij = (st + dr) / 2;
        double q =(x.X - v[mij].X);
        double w = (x.Y - v[mij].Y);
        if ( modul(q) <= Eps && modul(w) <= Eps){
            return mij;
        }

        if ( modul(q) <= Eps){//daca au acelsi x ma uit la y
            if (w > Eps) st = mij;
            else dr = mij;
            //continue;
        }else {//daca nu au acelasi x;
            if (q > Eps) st = mij;
            else dr = mij;
        }
    }
    double q = (x.X - v[dr].X);
    double w = (x.Y - v[dr].Y);
    if ( modul(q) <= Eps && modul(w) <= Eps) return dr;
    return -1;

}

void rezolva(){

    //sortez dupa x in caz de egalitate dupa y; iau 2 perechi de puncte si apoi le caut binar pe celelalte 2
    //presupun ca aia e o latura(aia de jos mai exact)

    int cnt = 0;
    for(int i=1; i<n; ++i){
        pair<double,double> A = make_pair(v[i].X, v[i].Y);
        for(int j=i+1; j<=n; ++j){
            pair<double, double> B = make_pair(v[j].X, v[j].Y);
            //b va fi tot timpul in dreapta  lui A
            double Dx = modul(A.X - B.X);
            double Dy = modul(A.Y - B.Y);

            pair<double,double> C = make_pair( B.X + Dy, B.Y + Dx );
            pair<double, double> D = make_pair( A.X + Dy, A.Y + Dx);

            //cout << A.X << " " << A.Y << " " << B.X << " " << B.Y << " " << C.X << " " << C.Y << " " << D.X << " " << D.Y << "\n";

            int ok = cb(C);
            int ok2 = cb(D);
            /*
            int ok2 = 0;
            for(int k=1; k<=n; ++k){
                double q = modul(v[k].X - D.X);
                double w = modul(v[k].Y - D.Y);
                if (q <= 0.0001 && w <=0.0001) ok2 = 1;
            }
            */
            if (ok != -1 && ok2 !=- 1) ++cnt;
        }
    }

    g << cnt << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}