Cod sursa(job #1140083)

Utilizator UNIBUC_Miriam_Bogdan_AlexCocaColaTeam UNIBUC_Miriam_Bogdan_Alex Data 11 martie 2014 18:40:02
Problema Patrate 3 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream f("patrate3.in");
ofstream g("patrate3.out");
int n, i, j, nrs;
int x, y, xm, ym, x3, y3, x4, y4, X, Y, semn;
pair<int, int> v[1010];
char s[30];

int cb(int x, int y){
    int p=1, u=n, m;
    while(p<=u)
    {
        m=p+(u-p)/2;
        if(v[m].first==x && v[m].second==y)
            return 1;
        if(v[m].first==x)
        {
            if(v[m].second<y)
                p=m+1;
            else
                u=m-1;
        }
        else
        {
            if(v[m].first<x)
                p=m+1;
            else
                u=m-1;
        }
    }
    return 0;
}

int cauta(int x, int y){
    for(int i=1; i<=n; i++)
        if(v[i].first==x && v[i].second==y)
            return 1;
    return 0;
}

inline int modul(int x){
    return ((-x)>x?(-x):x);
}

int main(){
    f>>n;
    for(i=1; i<=n; i++)
    {
        f.get();
        f.get(s+1, 25);
        x=strlen(s+1);
        j=1;
        X=0;
        semn=1;
        if(s[1]=='-')
            semn=-1, j++;
        while(s[j]!=' ')
        {
            if(s[j]=='.')
                j++;
            X=X*10+(s[j]-'0');
            j++;
        }
        X=X*semn;
        semn=1;
        j++;
        Y=0;
        if(s[j]=='-')
            semn=-1, j++;
        while(j<=x)
        {
            if(s[j]=='.')
                j++;
            Y=Y*10+(s[j]-'0');
            j++;
        }
        Y=Y*semn;
        v[i]=make_pair(X, Y);
    }
    sort(v+1, v+n+1);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            if(i!=j)
            {
                xm=(v[i].first+v[j].first)/2;
                ym=(v[i].second+v[j].second)/2;
                x=modul(xm-v[i].first);
                y=modul(ym-v[i].second);
                if(v[i].second<v[j].second)
                {
                    x3=xm+y;
                    y3=ym-x;
                    x4=xm-y;
                    y4=ym+x;
                }
                else
                {
                    x3=xm-y;
                    y3=ym-x;
                    x4=xm+y;
                    y4=ym+x;
                }
                if(cb(x3, y3)==1 && cb(x4, y4)==1)
                    nrs++;
            }
    }
    g<<nrs/2<<"\n";
    return 0;
}