Cod sursa(job #1758605)

Utilizator antanaAntonia Boca antana Data 17 septembrie 2016 15:34:10
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>
#include <ctype.h>
#include <algorithm>
#define MAXN 1000
#define MOD (1023)
#define T 10000

struct aa{
    int x, y;
}v[MAXN];

int r, lista[MOD][MOD], nxt[MAXN+1], val[MAXN+1];

inline void add(int ind)
{
    int mod1=(v[ind].x&MOD), mod2=(v[ind].y&MOD);

    val[++r]=ind;
    nxt[r]=lista[mod1][mod2];
    lista[mod1][mod2]=r;
}

inline bool check(aa aux)
{
    int mod1=(aux.x & MOD), mod2=(aux.y & MOD), p;
    p=lista[mod1][mod2];

    while(p)
    {
        if(v[val[p]].x == aux.x && v[val[p]].y == aux.y)
            return true;
        p=nxt[p];
    }

    return false;
}

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

inline int read(FILE *f)
{
    int nr=0, sg=1;
    char c;

    fscanf(f, "%c", &c);
    while(!isdigit(c) && c != '-') fscanf(f, "%c", &c);

    if(c == '-') sg*=-1, fscanf(f, "%c", &c);

    while(isdigit(c) || c == '.')
    {
        if(isdigit(c)) nr=nr*10+c-'0';
        fscanf(f, "%c", &c);
    }

    return nr*sg;
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("patrate3.in", "r");
    fout=fopen("patrate3.out", "w");

    int n, x0, y0, i, j, ans=0;
    aa aux1, aux2;

    fscanf(fin, "%d\n", &n);

    for(i=0;i<n;++i){
        x0=read(fin);
        y0=read(fin);
        v[i].x=x0 + T;
        v[i].y=y0 + T;
    }

    std::sort(v, v+n, cmp);

    for(i=0;i<n;++i)
        add(i);

    for(i=0;i<n-1;++i)
        for(j=i+1;j<n;++j)
            if(v[j].y >= v[i].y && v[i].x < v[j].x)
            {
                aux1.y=v[i].y - (v[j].x - v[i].x);
                aux1.x=v[i].x + (v[j].y - v[i].y);

                aux2.y=v[j].y - (v[j].x - v[i].x);
                aux2.x=v[j].x + (v[j].y - v[i].y);

                if(check(aux1) && check(aux2))
                    ans++;
            }

    fprintf(fout, "%d", ans);

    fclose(fin);
    fclose(fout);

    return 0;
}