Cod sursa(job #1776967)

Utilizator andru47Stefanescu Andru andru47 Data 11 octombrie 2016 22:55:29
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
#define per pair<float,float>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define eps 10e-5
#define MOD 7919
using namespace std;
const int NMAX = 1000 + 5;
int n,sol=0;
float x,y;
per a[NMAX];
vector < pair < float , pair < int, int > > > Hash[MOD];
inline float getdist(int i,int j)
{
    float x1 = a[i].f,y1=a[i].s,x2=a[j].f,y2=a[j].s;
    return (float(sqrt(1.0*(x2-x1)*(x2-x1)+1.0*(y2-y1)*(y2-y1))));
}

inline void add_hash(float dist,int i,int j)
{
    int mask = int(dist)%MOD;

    Hash[mask].pb(mp(dist,mp(i,j)));

    return ;
}

inline bool compara(float d1, float d2)
{
    if (abs(d1-d2)<eps) return true;
    return false;
}
inline bool check(float dist,int i,int j)
{
    int mask = int(dist)%MOD;
    for (auto &it : Hash[mask])
        if (compara(it.f,dist)==true&&i!=it.s.f&&j!=it.s.s&&i!=it.s.s&&j!=it.s.f)
        {
            float d1 = getdist(i,it.s.f);
            float d2 = getdist(j,it.s.s);
            float dd1 = getdist(i,it.s.s);
            float dd2 = getdist(i,it.s.f);
            if (compara(d1,d2)&&compara(d1,dist))return true;
            if (compara(dd1,dd2)&&compara(dd1,dist))return true;
        }
    return false;
}
int main()

{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    scanf("%d\n", &n);
    for (int i = 1; i<=n; ++i)
    {
        scanf("%f %f",&x, &y);
        x+=10000;
        y+=10000;
        a[i].f = x;
        a[i].s = y;
    }
    sort(a+1,a+n+1);
    for (int i = 1; i<=n; ++i)
        for (int j = i + 1; j<=n; ++j)
        {
            float dist=getdist(i,j);
            add_hash(dist,i,j);
        }
    for (int i = 1; i<=n; ++i)
        for (int j = i + 1; j<=n; ++j)
        {
            float dist = getdist(i , j);
            sol += check(dist,i,j);
        }
    printf("%d\n",sol/2);
    return 0;
}