Cod sursa(job #1733196)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 23 iulie 2016 22:55:23
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
pair<double,double> v[1505];
int n,ls,ld,m,sol,triunghiuri;
double sina,cosa,x,y,x01,y01,x11,y11;
bool egal(double x,double y)
{
    double z=(x-y);
    if (z<0) z=-z;
    if (z<=0.001) return 1;
    return 0;
}
int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].first,&v[i].second);
    }
    sort(v+1,v+n+1);
    cosa=0.5;
    sina=(sqrt((double)3))/2;
    for(int i=1;i<=(n-1);i++)
    {
        for(int j=(i+1);j<=(n);j++)
        {
            x=v[j].first;
            y=v[j].second;
            x01=v[i].first;
            y01=v[i].second;
            x11=x01+(x-x01)*cosa-(y-y01)*sina;
            y11=y01+(x-x01)*sina+(y-y01)*cosa;
            ls=i;
            ld=n;
            m=ls+(ld-ls)/2;
            sol=0;
            while (ls<=ld)
            {
                m=ls+(ld-ls)/2;
                if (m!=i && m!=j && egal(v[m].first,x11) && egal(v[m].second,y11))
                {
                    sol=m;
                    ls=ld+1;
                }
                    else
                if (v[m].first>x11 || (egal(v[m].first,x11) && v[m].second>y11))
                {
                    ld=m-1;
                }
                    else
                if (v[m].first<x11 || (egal(v[m].first,x11) && v[m].second<y11))
                {
                    ls=m+1;
                }
            }
            if (sol)
            {triunghiuri++;
        //    printf("%d %d %d\n",i,j,sol);
            }
        }
    }
    printf("%d\n",triunghiuri);
    return 0;
}