Cod sursa(job #592623)

Utilizator stef93Stefan Gilca stef93 Data 29 mai 2011 14:09:33
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <fstream>
#include <iostream>
#include <complex>
#include <vector>
#include <cmath>
#define eps 0.618033
#define M 1503
using namespace std;

const double s3=sqrt(3);
struct P{double x,y;};
P a[1509];
int n;
bool cmp(P u, P v)
{
     return u.x<v.x;
}
vector <P> H[999999];
int h2(pair<int,int> a)
{
    return(a.first*a.second)%M;
}
int h(double x,double y)
{
               pair<int,int> a;
               double pi;
               pi=(x-int(x))*eps;
               double pii;
               pii=pi-int(pi);
               a.first=int(pii*M);
               pi=(y-int(y))*eps;
               pii=pi-int(pi);
               a.second=int(pii*M);
               return h2(a);
}
int main()
{
    int i,j,nrtr=0;
    ifstream in("triang.in");
    ofstream out("triang.out");
    in>>n;
    for(i=0;i<n;i++)
    {
                    in>>a[i].x>>a[i].y;
                    H[h(a[i].x,a[i].y)].push_back(a[i]);
    }
    sort(a,a+n,cmp);
    complex<double> A,B,C,EPS;
    EPS.real()=(double)1/2;
    EPS.imag()=s3/2;
    for(i=0;i<n-2;++i)
    for(j=i+1;j<n-1;++j)
    {
                       // out<<a[i].x<<' '<<a[i].y<<'\n'<<a[j].x<<' '<<a[j].y<<'\n';
                       // double k=(-a[i].x+a[i].y*s3+a[j].x+a[j].y*s3)/2;
                        //double q=(-a[i].y-a[i].x*s3-a[j].x*s3+a[j].y)/2;
                        //out<<k<<' '<<q<<'\n';
                       /* A.real()=a[i].x;
                        A.imag()=a[i].y;
                        B.real()=a[j].x;
                        B.imag()=a[j].y;
                        C=(-A*EPS-B*EPS*EPS);
                        cout<<A<<'\n';
                        cout<<B<<'\n';
                        cout<<C<<'\n';
                        system("pause");*/
                        int y=h(C.real(),min(a[i].y,a[j].y));
                        for(int u=0;u<H[y].size();++u)
                        if(H[y][u].x==C.real()&&H[y][u].y==min(a[i].y,a[j].y))
                        {
                                                         nrtr++;
                                                         break;
                        }
    }
    out<<nrtr<<'\n';
    return 0;
}