Cod sursa(job #2130288)

Utilizator patcasrarespatcas rares danut patcasrares Data 13 februarie 2018 16:26:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#define eps 1e-6
#define DN 1505
#define x first
#define y second
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
int n,rez,st,dr,m;
pair<long double,long double>a[DN];
long double a1,b1,c1,a2,b2,c2,l,c,d,ar;
long double dist(int p1,int p2)
{
    return (a[p1].x-a[p2].x)*(a[p1].x-a[p2].x)+(a[p1].y-a[p2].y)*(a[p1].y-a[p2].y);
}
int cautare()
{
    c=(c2*a1-c1*a2)/(b1*a2-b2*a1);
    if(abs(a1)>eps)
        l=(-c1-b1*c)/a1;
    else
        l=(-c2-b2*c)/a2;
    st=1;
    dr=n;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(l-a[m].x>eps||(abs(a[m].x-l)<eps&&c-a[m].y>eps))
            st=m+1;
        else
            dr=m;
    }
    if(abs(l-a[st].x)<eps&&abs(c-a[st].y)<eps)
        return 1;
    return 0;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            d=dist(i,j);
            ar=(d*sqrt(3))/2;
            a1=2*(a[j].x-a[i].x);
            b1=2*(a[j].y-a[i].y);
            c1=-a[j].x*a[j].x+a[i].x*a[i].x-a[j].y*a[j].y+a[i].y*a[i].y;
            a2=a[i].y-a[j].y;
            b2=a[j].x-a[i].x;
            c2=ar+a[i].x*a[j].y+a[j].x*a[i].y;
            if(cautare())
            {
               // cout<<l<<' '<<c<<'\n';
                rez++;
            }
            c2=-ar+a[i].x*a[j].y+a[j].x*a[i].y;
            if(cautare())
            {
            //    cout<<l<<' '<<c<<'\n';
                rez++;
            }
        }
    fout<<rez/3;
}