Cod sursa(job #719224)

Utilizator andreii1Ilie Andrei andreii1 Data 21 martie 2012 17:00:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;

int n,i,j,cnt;
float xc,yc,m,p,s,t;

struct punct{float x;float y;}a[1510];

int compare(punct m,punct n)
{
    if(m.x==n.x)return(m.y<n.y); else return(m.x<=n.x);
}

float modul(float x)
{
    if(x>0)return x; return -x;
}

int cautb(float x,float y, int st)
{
    int dr=n;
    int mij=(st+dr)/2;
    int gasit=0;
    while(st<dr&&!gasit)
    {
        if (modul(a[mij].x-x)<0.001&&modul(a[mij].y-y)<0.001) gasit=1;
        else
        if(a[mij].x>x&&modul(a[mij].x-x)>0.001){dr=mij-1;mij=(st+dr)/2;}
        else
        if(a[mij].x<x&&modul(a[mij].y-y)>0.001){st=mij+1;mij=(st+dr)/2;}
        else
        if(a[mij].y<y){st=mij+1;mij=(st+dr)/2;}
        else
        if(a[mij].y>y){dr=mij-1;mij=(st+dr)/2;}
    }
    if(st==dr&&modul(a[mij].x-x)<0.001&&modul(a[mij].y-y)<0.001)gasit=1;
    return gasit;
}

int main()
{

    FILE *f=fopen("triang.in","r");
    FILE *g=fopen("triang.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%f %f",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,compare);
    for(i=1;i<=n-2;i++)
    for(j=i+1;j<=n-1;j++)
    {
        if(modul(a[i].y-a[j].y)<0.001)
        {
            xc=(a[i].x+a[j].x)/2;
            yc=a[i].y+modul(a[i].x-a[j].x)*sqrt(3)/2;
            if(xc+0.001>a[1].x&&yc+0.001>a[1].y)
            if(xc<0.001+a[n].x&&yc<0.001+a[n].y)
            if(cautb(xc,yc,j+1))cnt++;

            yc=a[i].y-modul(a[i].x-a[j].x)*sqrt(3)/2;
            if(xc+0.001>a[1].x&&yc+0.001>a[1].y)
            if(xc<0.001+a[n].x&&yc<0.001+a[n].y)
            if(cautb(xc,yc,j+1))cnt++;
        }
        else
        if(modul(a[i].x-a[j].x)<0.001)
        {
            yc=(a[i].y+a[j].y)/2;
            xc=a[i].x+modul(a[i].y-a[j].y)*sqrt(3)/2;
            if(xc<0.001+a[n].x&&yc<0.001+a[n].y)
            if(xc+0.001>a[1].x&&yc+0.001>a[1].y)
            if(cautb(xc,yc,j+1))cnt++;
            xc=a[i].x-modul(a[i].y-a[j].y)*sqrt(3)/2;
            if(xc+0.001>a[1].x&&yc+0.001>a[1].y)
            if(xc<0.001+a[n].x&&yc<0.001+a[n].y)
            if(cautb(xc,yc,j+1))cnt++;
        }
        else
        {
        t=3*((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))/4;
        s=(a[i].x-a[j].x)/(a[j].y-a[i].y);
        m=sqrtf(t/(1+s*s));
        p=m*s;
        xc=m+(a[i].x+a[j].x)/2;
        yc=p+(a[i].y+a[j].y)/2;
        if(xc<0.001+a[n].x&&yc<0.001+a[n].y)
        if(xc+0.001>a[1].x&&yc+0.001>a[1].y)
        if(cautb(xc,yc,j+1))cnt++;
        m=-sqrtf(t/(1+s*s));
        p=m*s;
        xc=m+(a[i].x+a[j].x)/2;
        yc=p+(a[i].y+a[j].y)/2;
        if(xc<0.001+a[n].x&&yc<0.001+a[n].y)
        if(xc+0.001>a[1].x&&yc+0.001>a[1].y)
        if(cautb(xc,yc,j+1))cnt++;
        }
    }
    fprintf(g,"%d",cnt);
    fclose(f);
    fclose(g);
    return 0;
}