Cod sursa(job #291993)

Utilizator DraStiKDragos Oprica DraStiK Data 30 martie 2009 17:36:52
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <algorithm>
#include <math.h>
#define DIM 1505
using namespace std;
struct punct {double x,y;} a[DIM];
double x,y11,y22;
int n,nrt;
void read ()
{
    int i;
    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
        scanf ("%lf%lf",&a[i].x,&a[i].y);
}
void det (int i,int j,double x,double &y11,double &y22)
{
    double rp;
    rp=(a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y)-(a[i].x-x)*(a[i].x-x);
    y11=a[i].y-sqrt (rp);
    y22=a[i].y+sqrt (rp);
}
int cbin (int st,int dr,double x,double y)
{
    int mij;
    while (st<=dr)
    {
        mij=st+(dr-st)/2;
		if (a[mij].x==x && a[mij].y-y<1e-3)
            return 1;
        else if (a[mij].x<x || (a[mij].x==x && a[mij].y<y))
            st=mij+1;
        else if (a[mij].x>x || (a[mij].x==x && a[mij].y>y))
            dr=mij-1;
    }
    return 0;
}
void solve ()
{
    int i,j;
    for (i=1; i<n; ++i)
        for (j=i+1; j<=n; ++j)
		{
            x=(a[i].x+a[j].x)/2;
            det (i,j,x,y11,y22);
            if (cbin (i,j,x,y11))
                ++nrt;
            if (cbin (i,j,x,y22))
                ++nrt;
        }
    printf ("%d",nrt);
}
int cmp (punct a,punct b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}
int main ()
{
    freopen ("triang.in","r",stdin);
    freopen ("triang.out","w",stdout);
    read ();
    sort (a+1,a+n+1,cmp);
    solve ();
    return 0;
}