Cod sursa(job #1072499)

Utilizator Aleks10FMI - Petrache Alex Aleks10 Data 4 ianuarie 2014 15:56:17
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.06 kb
#include <iostream>
#include <set>
#include <map>
#include <fstream>
#include <algorithm>


using namespace std;
#define x first
#define y second

pair<double,double> punct[1001];
map < pair<int,int>, int > H;
int n;

bool cauta(pair<double,double> p){
    int pas=(1<<10),i=0;
   // cout<<p.x<<" "<<p.y<<endl;
    for(i=0;pas;pas=pas/2){
        //cout<<punct[i+pas].x<<" ";
        if((i+pas)<=n && (punct[i+pas]<=p)){
            i=i+pas;
        }
    }

    //cout<<punct[i].x<<"S ";
    if(punct[i]==p)
        return 1; //p.first;
    else return 0;
}

int convert (string s) {
    int x = 0, sign = ((s[0] == '-') ? -1 : 1);
    for (unsigned i = 0; i < s.size(); ++i)
        if (s[i] >= '0' && s[i] <= '9')
            x = x * 10 + s[i] - '0';
    return x * sign;
}

int main()
{
    int i,j;
    ifstream f("patrate3.in");
    ofstream g("patrate3.out");
    f>>n;
    for(i=1;i<=n;i++){
        string s[2];
        f >> s[0] >> s[1];
        int a = convert(s[0]), b = convert(s[1]);
        //cout<<a<<" "<<b<<endl;
        //f>>punct[i].x>>punct[i].y;
        punct[i].x=a;
        punct[i].y=b;
        H[make_pair(a,b)]=i;
    }
    sort(punct+1,punct+n+1);

    double mijx,mijy,dx,dy, x2,y2, x3,y3;
    int nr=0;
    for(i=1;i<=n-1;i++){
        for(j=i+1;j<=n;j++){
          //  cout<<punct[i].x<<" cu "<<punct[j].x<<endl;
            mijx=(punct[i].x+punct[j].x)/2;
            mijy=(punct[i].y+punct[j].y)/2;
            //cout<<mijx<<endl;
            dx=abs(mijx-punct[i].x);
            dy=abs(mijy-punct[i].y);
            //cout<<dx<<endl;
            if(punct[i].y<punct[j].y){
                x2=mijx+dy;
                y2=mijy-dx;

                x3=mijx-dy;
                y3=mijy+dx;
            }
            else{
                x2=mijx-dy;
                y2=mijy-dx;

                x3=mijx+dy;
                y3=mijy+dx;
            }

            if(cauta(make_pair(x2,y2)) && cauta(make_pair(x3,y3)))
                nr++;
        }
    }
    g<<nr/2;
    return 0;
}