Cod sursa(job #1140312)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 11 martie 2014 21:45:39
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("patrate3.in");
ofstream fout ("patrate3.out");

int n,m,i,j,sol,st,dr,mid,semn,x1,x2,yy1,yy2,xg,yg;

char s[20];

struct punct {
    int x;
    int y;
}v[1010];

int cautb (int x,int y) {

    st=1;dr=n;

    while(st<=dr) {
        mid=st+(dr-st)/2;
        if(v[mid].x>x)
            dr=mid-1;
        else
            if(v[mid].x<x)
                st=mid+1;
            else
                if(v[mid].y>y)
                    dr=mid-1;
                else
                    st=mid+1;
    }
    if(v[dr].x!=x || v[dr].y!=y)
        return 0;
    return 1;
}

bool cmp(const punct &a, const punct &b) {
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int main () {

    fin>>n;

    for (i=1;i<=n;i++) {
        fin>>s;
        semn=1;
        if (s[0]=='-')
            semn=-1;

        for (j=0;s[j]!=0;j++)
            if (s[j]>='0' && s[j]<='9')
                v[i].x=v[i].x*10+(s[j]-'0');
        v[i].x*=semn;
        v[i].x*=2;

        fin>>s;
        semn=1;
        if (s[0]=='-')
            semn=-1;

        for (j=0;s[j]!=0;j++)
            if (s[j]>='0' && s[j]<='9')
                v[i].y=v[i].y*10+(s[j]-'0');
        v[i].y*=semn;
        v[i].y*=2;
    }
    sort (v+1,v+n+1,cmp);

    for (i=1;i<n;i++) {
        for (j=i+1;j<=n;j++) {

            xg=(v[i].x+v[j].x); yg=(v[i].y+v[j].y);
            xg/=2;   yg/=2;
            x1=xg-(v[j].y-yg);  yy1=yg+(xg-v[i].x);
            x2=xg+(v[j].y-yg);  yy2=yg-(xg-v[i].x);

            if (cautb(x1,yy1) && cautb(x2,yy2))
                sol++;
        }
    }

    fout<<sol/2<<"\n";

    return 0;
}