Cod sursa(job #2539897)

Utilizator As932Stanciu Andreea As932 Data 6 februarie 2020 14:59:29
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 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,ans,st,dr,mid;
double a1,b1,c1,a2,b2,c2,l,c,d,ar;
pair<double,double>v[DN];

double dist(int i,int j)
{
    return (v[i].x-v[j].x)*(v[i].x-v[j].x)-(v[i].y-v[j].y)*(v[i].y-v[j].y);
}

void citire()
{
    fin>>n;

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

bool bin()
{
    c=(c2*a1-c1*a2)/(b1*a2-b2*a1);
    if(fabs(a1)>eps)
        l=(-c1-b1*c)/a1;
    else
        l=(-c2-b2*c)/a2;

    st=1,dr=n;

    while(st<dr)
    {
        mid=(st+dr)/2;

        if(l-v[mid].x>eps || (fabs(v[mid].x-l)<eps && c-v[mid].y>eps))
            st=mid+1;
        else
            dr=mid;
    }
    if(fabs(l-v[st].x)<eps && fabs(c-v[st].y)<eps)
        return true;

    return false;
}

int main()
{
    citire();
    sort(v+1,v+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*(v[j].x-v[i].x);
            b1=2*(v[j].y-v[i].y);
            c1=-v[j].x*v[j].x+v[i].x*v[i].x-v[j].y*v[j].y+v[i].y*v[i].y;

            a2=v[i].y-v[j].y;
            b2=v[j].x-v[i].x;
            c2=ar+v[i].x*v[j].y-v[j].x*v[i].y;
            if(bin())
                ans++;
            c2=-ar+v[i].x*v[j].y-v[j].x*v[i].y;
            if(bin())
                ans++;
        }

    fout<<ans;
    return 0;
}