Cod sursa(job #2581871)

Utilizator RazvanucuPopan Razvan Calin Razvanucu Data 15 martie 2020 21:47:06
Problema Triang Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <math.h>
using namespace std;

ifstream f("triang.in");
ofstream g("triang.out");

const double Err=0.0001;

struct pct
{
    double x,y;
} p[1505];
int n,nrtriang;
int AbsoluteValue(double x)
{
    if(x<0)
        return -x;
    return x;
}
bool comp(pct a,pct b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int bin(double x,double y)
{
    int st=1, dr=n, mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (AbsoluteValue(p[mij].x-x)<=Err && AbsoluteValue(p[mij].y-y)<=Err)
            return 1;
        if (p[mij].x<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>p[i].x>>p[i].y;

    sort(p+1,p+n+1,comp);

    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {

            double m,xm,ym,x1,y1,x2,y2,dist;
            pct a,b;

            a.x=p[i].x;
            a.y=p[i].y;

            b.x=p[j].x;
            b.y=p[j].y;

            xm=(a.x+b.x)/2;
            ym=(a.y+b.y)/2;

            dist=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
            dist*=3;

            if(AbsoluteValue(a.x-b.x)<=Err)
            {
                y1=ym;
                y2=ym;

                x1=xm+0.5d*sqrt(dist);
                x2=xm-0.5d*sqrt(dist);
            }
            else
            {

                m=(b.y-a.y)/(b.x-a.x);

                y1=ym-0.5d*sqrt(dist/(1+m*m));
                x1=xm+0.5d*m*sqrt(dist/(1+m*m));

                y2=ym+0.5d*sqrt(dist/(1+m*m));
                x2=xm-0.5d*m*sqrt(dist/(1+m*m));


            }

            nrtriang+=bin(x1,y1);
            nrtriang+=bin(x2,y2);


        }
    g<<nrtriang/3;
    return 0;
}