Cod sursa(job #2551782)

Utilizator DesertChuStefan Andrei DesertChu Data 20 februarie 2020 10:37:21
Problema Triang Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

FILE*f=fopen("triang.in","r");
FILE*g=fopen("triang.out","w");

struct punct
{
    double x,y;
}v[1501];

int cmp(punct a,punct b) // sortare dupa x si la x egal dupa y
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
long long n;

int caut(double x1,double y1,int j) //  caut binar punctul (x1,y1 de la v[j] la v[n]
{
    int p,u,m;
        p=j+1;
        u=n;
        while (p<=u)
        {
            m=(p+u)/2;
            if (fabs(v[m].x-x1)<0.001&&fabs(v[m].y-y1)<0.001) return 1;
            else if (v[m].x>x1||(fabs(v[m].x-x1)<0.001&&v[m].y>y1)) u=m-1;
            else p=m+1;
        }
        return 0;
}


int main()
{
    long long nr=0,i,j;
    double l,d,xm,ym,x,y,t,t1;
    fscanf(f,"%lld",&n);
    for (i=1;i<=n;i++)
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
    {
        xm=(v[i].x+v[j].x)/2;
        ym=(v[i].y+v[j].y)/2;
        l=sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y));
        d=l*sqrt(3)/2;
        printf("%lf %lf\n",l,d);
        if (fabs(v[j].y-v[i].y)<0.001)
            {
                x=xm;
                y=ym+d;if (caut(x,y,j)) nr++;
                y=ym-d;if (caut(x,y,j)) nr++;
            }
        else
        {
        t=(v[i].x-v[j].x)/(v[j].y-v[i].y);
        /*t1=(v[j].y-v[i].y)/(v[j].x-v[i].x);
        t=-1/t1;*/
        x=xm-d/sqrt(1+t*t);
        y=(x-xm)*t+ym;
        printf("%lf %lf %lf\n",t,x,y);
        if (caut(x,y,j)) nr++;
        x=xm+d/sqrt(1+t*t);
        y=(x-xm)*t+ym;
        printf("%lf %lf %lf\n",t,x,y);
        if (caut(x,y,j)) nr++;
        }
    }
    fprintf(g,"%lld",nr);
    fclose(g);
    fclose(f);
    return 0;
}