Cod sursa(job #1675672)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 5 aprilie 2016 14:53:24
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#define pb push_back
#define mp make_pair
#define MAXN 1501
#define INFILE "triang.in"
#define OUTFILE "triang.out"
#define eps 0.001
#define x first
#define y second
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
int n,k,i,j,l;
//70 puncte - O(N^3)
/*double v[MAXN][2],aux;
inline double dist(double x1, double y1, double x2, double y2)
{
    return ((x1-x2)*(x1-x2)+(y2-y1)*(y2-y1));
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i][0]>>v[i][1];
    for(i=1;i<n-1;i++)
        for(j=i+1;j<n;j++)
        {
            aux=dist(v[i][0],v[i][1],v[j][0],v[j][1]);
            for(l=j+1;l<=n;l++)
                if(abs(aux-dist(v[i][0],v[i][1],v[l][0],v[l][1]))<eps&&abs(aux-dist(v[j][0],v[j][1],v[l][0],v[l][1]))<eps)k++;
        }
    g<<k;
    f.close();
    g.close();
    return 0;
}*/
//Pe exemplu da corect, pe infoarena 9 gresite si 1 TLE, nu stiu care ar putea fi problema
vector<pair<double,double> >v;
vector<pair<double,double> >::iterator it,jt,aux;
double x,y,A,sina,cosa,d,sqrt3,xres,yres;
inline bool comp(const pair<double,double>& a,const pair<double,double>& b)
{
    if(abs(a.x-b.x)<eps)return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    f>>n;
    sqrt3=sqrt((double)3);
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        v.pb(mp(x,y));
    }
    sort(v.begin(),v.end(),comp);
    for(it=v.begin();it!=v.end();it++)
        for(jt=it+1;jt!=v.end();jt++)
        {
            d=sqrt((it->x-jt->x)*(it->x-jt->x)+(it->y-jt->y)*(it->y-jt->y));
            A=atan((jt->y-it->y)/(jt->x-it->x));
            cosa=cos(A);
            sina=sin(A);

            x=(it->x+jt->x)/2;
            y=(it->y+jt->y)/2+d*sqrt3/2;
            xres=it->x+(x-it->x)*cosa-(y-it->y)*sina;
            yres=it->y+(x-it->x)*sina+(y-it->y)*cosa;

            aux=upper_bound(v.begin(),v.end(),mp(xres,yres),comp);
            if(aux!=v.begin())
            {
                aux--;
                if(abs(aux->x-xres)<eps&&abs(aux->y-yres)<eps)k++;
            }

            x=(it->x+jt->x)/2;
            y=(it->y+jt->y)/2-d*sqrt3/2;
            xres=it->x+(x-it->x)*cosa-(y-it->y)*sina;
            yres=it->y+(x-it->x)*sina+(y-it->y)*cosa;

            aux=upper_bound(v.begin(),v.end(),mp(xres,yres),comp);
            if(aux!=v.begin())
            {
                aux--;
                if(abs(aux->x-xres)<eps&&abs(aux->y-yres)<eps)k++;
            }
        }
    g<<k;
    f.close();
    g.close();
    return 0;
}