Cod sursa(job #1322181)

Utilizator ThomasFMI Suditu Thomas Thomas Data 19 ianuarie 2015 20:39:35
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;

#define NMax 1005
#define epsilon 0.0001f

ifstream f("patrate3.in");
ofstream g("patrate3.out");

int n,sol;
int dnr;
int ct[NMax*NMax];

struct point
{
    double x,y;

    bool operator < (const point &t) const
    {
        if(t.x == x) return t.y < y;
        else return t.x < x;
    }

} P[NMax];
struct line
{
    point a,b;
    double l;

    bool operator < (const line &t) const
    {
        if(t.l == l) return t.a < a;
        else return t.l > l;
    }

} D[NMax*NMax];

unordered_map<point, int> Hash;
unordered_map<point, int>::iterator it;

int main()
{
    int i,j;

    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>P[i].x>>P[i].y;
    }

    for(i=1;i<n;++i) for(j=i+1;j<=n;++j)
    {
        ++dnr;
        if((P[i].x == P[j].x && P[i].y < P[j].y) || (P[i].x < P[j].x))
        {
            D[dnr].a = P[i];
            D[dnr].b = P[j];
        }
        else
        {
            D[dnr].b = P[i];
            D[dnr].a = P[j];
        }
        D[dnr].l = sqrt( (D[dnr].b.x - D[dnr].a.x)*(D[dnr].b.x - D[dnr].a.x) + (D[dnr].b.y - D[dnr].a.y)*(D[dnr].b.y - D[dnr].a.y) );
    }

    sort(D+1,D+dnr+1);

    int key = 0;

    for(i=1;i<=dnr;++i)
    {
        //g<<"\n"<<D[i].l;
        if(D[i].l - D[i-1].l < epsilon)
        {
            //g<<"<-- ";
            it = Hash.find(D[i].a);
            if(it == Hash.end())
            {
                Hash[D[i].a] = ++key;
                ct[key] = 1;
            }
            else ct[(*it).second]++;

            it = Hash.find(D[i].b);
            if(it == Hash.end())
            {
                Hash[D[i].b] = ++key;
                ct[key] = 1;
            }
            else ct[(*it).second]++;
        }
        else
        {
            int p = 0;
            for(j=1;j<=key;++j) p += ct[j]/2, ct[j] = 0;

            sol += p/4;
            Hash.clear();

            it = Hash.find(D[i].a);
            if(it == Hash.end())
            {
                Hash[D[i].a] = ++key;
                ct[key] = 1;
            }
            else ct[(*it).second]++;

            it = Hash.find(D[i].b);
            if(it == Hash.end())
            {
                Hash[D[i].b] = ++key;
                ct[key] = 1;
            }
            else ct[(*it).second]++;
        }
    }

    g<<sol<<"\n";

    f.close();
    g.close();
    return 0;
}