Cod sursa(job #1072498)

Utilizator Aleks10FMI - Petrache Alex Aleks10 Data 4 ianuarie 2014 15:56:00
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 6.29 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];
//unordered_set<pair<double,double> > unmap;
//set < pair<int,int> > H;
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);
   // for(i=1;i<=n;i++)
     //   cout<<punct[i].x<<" "<<punct[i].y<<endl;
    //cout<<cauta(make_pair(26.695,17.275));
    //cout<<cauta(make_pair(26.695 ,17.275));
    //cout<<(H.find(make_pair(91.32, 13.36))!=H.end());

    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;
            }
          /*  int Y = punct[i].x - punct[j].x, X = punct[i].y - punct[j].y;
            map <pair<int,int>, int> :: iterator it1, it2, it3, it4;
            it1 = H.find(make_pair (punct[i].x + X, punct[i].y - Y));
            it2 = H.find(make_pair (punct[j].x + X, punct[j].y - Y));
            it3 = H.find(make_pair (punct[i].x - X, punct[i].y + Y));
            it4 = H.find(make_pair (punct[j].x - X, punct[j].y + Y));*/
            //if (it1 != H.end() && it2 != H.end()) {p++;}
            //if (it3 != H.end() && it4 != H.end()) {p++;}

           // cout<<"are"<<x2<<" "<<y2<<" & "<<x3<<" "<<y3<<endl;
           // cout<<"are"<<punct[i].x + X<<" "<<punct[i].y - Y<<" & "<<x3<<" "<<y3<<endl;
          //  cout<<(it1 != H.end() && it2 != H.end())<<" "<<(it3 != H.end() && it4 != H.end())<<endl;
          //  cout<<x2<<" "<<y2<<" si "<<x3<<" "<<y3<<endl;
         //   cout<<cauta(make_pair(x2,y2));
         //   cout<<" "<<cauta(make_pair(x3,y3))<<endl;
            //cauta(make_pair(x2,y2));
            if(cauta(make_pair(x2,y2)) && cauta(make_pair(x3,y3)))
                nr++;
           // cout<<(H.find(make_pair(x2*10000, y2*10000))!=H.end())<<" "<<(H.find(make_pair(x3*10000, y3*10000))!=H.end())<<endl;
         /*   map <pair<int,int>, int> :: iterator it1, it2, it3, it4;
            it1 = H.find(make_pair (x2*1000, y2*1000));
            it2 = H.find(make_pair (x3*1000, y3*1000));
            cout<<(it1!=H.end())<<" "<<(it2!=H.end())<<endl;*/
            //it3 = M.find(make_pair (a.first - X, a.second + Y));
            //it4 = M.find(make_pair (b.first - X, b.second + Y));

        }
    }
   // cout<<cauta(make_pair(26.695 ,17.275));
    g<<nr/2;
 /*   x2=515700;
    y2=109400;
    cout<<(H.find(make_pair( x2,y2))!=H.end());*/
    //for(i=0;i<n;i++)
      //  cout<<punct[i].x<<" "<<punct[i].y<<endl;
    return 0;
}

/*#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <algorithm>


using namespace std;

unordered_map<double,int> unmap;
unordered_set<double> unset;
struct punct{
    double x;
    double y;
};
punct v[1001],p;
int contor=0;

int main()
{
    int n,i;
    ifstream f("patrate3.in");
    ofstream g("patrate3.out");
    f>>n;
    double xx,yy;
    for(i=1;i<=n;i++){
        f>>xx>>yy;
        p.x=xx;
        p.y=yy;
        v[i]=p;

        unmap.insert(make_pair<double&,int&>(xx,i));
        unmap.insert(make_pair<double&,int&>(yy,i));
    }

    //sort(v+1);
    //sort(v+n+1);
    //cout<<(unmap.find(2.5212)!=unmap.end());
    int j;
    punct a,b,c,d;
    for(i=1;i<=n-1;i++){
        for(j=i+1;j<=n;j++){
            if(i!=j){
            a=v[i];
            b=v[j];
            c.x=a.x+(a.y-b.y);
            c.y=a.y+(b.x-a.x);

            d.x=b.x+(a.y-b.y);
            d.y=b.y+(b.x-a.x);

  //          cout<<i<<" cu "<<j<<" face C("<<c.x<<", "<<c.y<<") si D("<<d.x<<", "<<d.y<<")"<<'\n';
            int ic,id;
            unordered_map<double,int>::const_iterator got = unmap.find (c.x);
            if ( got != unmap.end() )
                ic=got->second;
            //std::cout << got->first << " is " << got->second;
//cout<<endl;
            got=unmap.find(c.y);
            if ( got != unmap.end() )
                if(ic==got->second){
  //                  cout<<"c gasit"<<ic<<" cu "<<a.x<<","<<a.y<<" si"<<b.x<<","<<b.y<<" hai si d care e"<<d.x;
                    contor++;
                }
//cout<<endl;
    //        cout<<(unmap.find(d.x)!=unmap.end())<<"M"<<d.x;
            got=unmap.find(d.x);
            if ( got != unmap.end() )
                id=got->second;
  //          cout<<id;
//cout<<endl;
            got=unmap.find(d.y);
            if ( got != unmap.end() )
                if(id==got->second){
        //            cout<<"d gasit"<<id<<" cu "<<a.x<<","<<a.y<<" si"<<b.x<<","<<b.y<<" hai si c care e"<<c.x;
                    contor++;
                }

            //cout<<(unmap.find(c.y)!=unmap.end());
            }
        }
      //  cout<<endl;
    }
    g<<contor;
    return 0;
}
*/