Cod sursa(job #1674085)

Utilizator mateibanuBanu Matei Costin mateibanu Data 4 aprilie 2016 12:59:27
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}



int main()
{
    int n,nr=0,m,p,u,i,j,ok;
    double l,d,xm,ym,x,y,t;
    fscanf(f,"%d",&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))+sqrt((v[i].y-v[j].y)*(v[i].y-v[j].y));
        d=l*sqrt(3)/2;
        t=(v[i].x-v[j].x)/(v[j].y-v[i].y);
        x=xm-d/sqrt(1+t*t);
        y=(x-xm)*t+ym;
        p=1;
        u=n;
        ok=1;
        while (p<u&&ok)
        {
            m=(p+u)/2;
            if (v[m].x<x||(fabs(v[m].x-x)<0.001&&v[m].y<y)) u=m-1;
            else if (v[m].x>x||(fabs(v[m].x-x)<0.001&&v[m].y>y)) p=m+1;
            else if (fabs(v[m].x-x)<0.001&&fabs(v[m].y-y)<0.001) ok=0;
        }
        if (!ok) nr++;

        t=(v[i].x-v[j].x)/(v[j].y-v[i].y);
        x=xm+d/sqrt(1+t*t);
        y=(x-xm)*t+ym;
        p=1;
        u=n;
        ok=1;
        while (p<u&&ok)
        {
            m=(p+u)/2;
            if (v[m].x<x||(fabs(v[m].x-x)<0.001&&v[m].y<y)) u=m-1;
            else if (v[m].x>x||(fabs(v[m].x-x)<0.001&&v[m].y>y)) p=m+1;
            else if (fabs(v[m].x-x)<0.001&&fabs(v[m].y-y)<0.001) ok=0;
        }
        if (!ok) nr++;
    }
    fprintf(g,"%d",nr);
    fclose(g);
    fclose(f);
    return 0;
}