Cod sursa(job #1303312)

Utilizator costyv87Vlad Costin costyv87 Data 27 decembrie 2014 20:51:56
Problema Patrate 3 Scor 65
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.9 kb
#include <cstdio>
#include <math.h>
#include <list>
#define db (double)
#define md 666013
#define PI 3.14159265
FILE *f,*g;
using namespace std;

struct cp{
            double x,y;
            cp() {}
            cp (double X,double Y)
            {
                x = X;
                y = Y;
            }
        };

cp v[1010],mij,m1,m2;
double an1,an2;
int n,i,j,res;
list <cp> H[md];

int key_hash(cp val)
{
    int x,y;

    x = (int) val.x * 1000;
    y = (int) val.y * 1000;
    if (x<0) x= -x;
    if (y<0) y= -y;

    return ( (x+y)%md);

}

void insert_hash(cp val)
{
    int key = key_hash(val);
    list<cp>::iterator it;

    H[key].push_back(val);
}

double abs(double x)
{
    if (x<0) return -x;
    return x;
}

bool find_hash(cp val)
{
    int key = key_hash(val);
    list<cp>::iterator it;

    for (it = H[key].begin();it!=H[key].end();it++)
        if (abs( db (*it).x - val.x)< 0.000000001 && abs( db (*it).y - val.y)< 0.00000001)
            return true;
    return false;
}

int main()
{
    f=fopen("patrate3.in","r");
    g=fopen("patrate3.out","w");


    fscanf(f,"%d",&n);

    for (i=1;i<=n;i++)
    {
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
        insert_hash(v[i]);
    }

    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++)
        {
            mij = cp(  db (db v[i].x+v[j].x)/2 , db (db v[i].y + v[j].y)/2);



            m1.x =  db 0* (db v[i].x-mij.x) - db 1 * (db v[i].y-mij.y) + mij.x;
	        m1.y =  db 1* (db v[i].x-mij.x) + db 0 * (db v[i].y-mij.y) + mij.y;

	        m2.x =  db 0 * (db v[i].x-mij.x) - db -1 * (db v[i].y-mij.y) + mij.x;
	        m2.y =  db -1 * (db v[i].x-mij.x) + db 0 * (db v[i].y-mij.y) + mij.y;

            if (find_hash(m1) == true && find_hash(m2) == true)
            {
                res++;
            }
        }

    fprintf(g,"%d",res/2);

    return 0;
}