Cod sursa(job #1199169)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 18 iunie 2014 14:38:34
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <fstream>
#include <cmath>
#include <list>

#define mod 666013
#define eps 0.001
const double phi=sqrt(3)-1;
const double c_rot=sqrt(3)/2;
const double c=sqrt(5);

using namespace std;

inline double frac(double x)
{
    return (x-floor(x));
}

struct punct
{
    double x,y;

    punct (double a=0,double b=0)
    {
        x=a;
        y=b;
    }

    inline double hash()
    {
        return (c*x+y);
    }

    inline bool operator==(const punct &b)
    {
        return (fabs(x-b.x)<eps && fabs(y-b.y)<eps);
    }
}v[1505];

inline punct rotccw60(punct a,punct b)
{
    return punct((b.x-a.x)/2-(b.y-a.y)*c_rot+a.x,(b.x-a.x)*c_rot+(b.y-a.y)/2+a.y);
}

inline punct rotcw60(punct a,punct b)
{
    return punct((b.x-a.x)/2+(b.y-a.y)*c_rot+a.x,-(b.x-a.x)*c_rot+(b.y-a.y)/2+a.y);
}

list<punct> h[mod];
inline void insert(punct x)
{
    double t=x.hash();
    int b=(int)(mod*(frac(t*phi)));

    for(list<punct>::iterator it=h[b].begin();it!=h[b].end();it++)
        if(*it==x)
            return;
    h[b].push_back(x);
}

inline bool exista(punct x)
{
    double t=x.hash();
    int b=(int)(mod*(frac(t*phi)));

    for(list<punct>::iterator it=h[b].begin();it!=h[b].end();it++)
        if(*it==x)
            return 1;
    return 0;
}

int main()
{
    ifstream cin("triang.in");
    ofstream cout("triang.out");

    int n=0;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        insert(v[i]);
    }

    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            ans+=(exista(rotccw60(v[i],v[j])));
            ans+=(exista(rotcw60(v[i],v[j])));
        }

    ans/=3;
    cout<<ans<<'\n';

    cin.close();
    cout.close();
    return 0;
}