Cod sursa(job #2586572)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 21 martie 2020 10:39:06
Problema Triang Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 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.001;
 
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;
}