Cod sursa(job #1458813)

Utilizator tudor_bonifateTudor Bonifate tudor_bonifate Data 8 iulie 2015 15:20:05
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define eps 10e-3
#define rad3 1.7320508075688772935
using namespace std;
struct punct
{
    double x;
    double y;
};
double x1,y3,x2,y4,d,Sin,Cos;
int nrt,n,i,j;
punct a[1501];
bool cmp(punct a, punct b)
{
    if (a.x<b.x) return true;
    else
    {
        if (a.x>b.x) return false;
        else
        {
            if (a.y<b.y) return true;
            else return false;
        }
    }
}
int cautare_binara(double xf, double yf, int j)
{
    int st=j+1;
    int dr=n;
    int mij=(st+dr)/2;
    while (!(fabs(a[mij].x-xf)<eps && fabs(a[mij].y-yf)<eps) && st<=dr)
    {
        if (a[mij].x>xf) dr=mij-1;
        else if (a[mij].x<xf) st=mij+1;
        else
        {
            if (a[mij].y>yf) dr=mij-1;
            else if (a[mij].y<yf) st=mij+1;
        }
        mij=(st+dr)/2;
    }
    if (st>dr) return -1;
    else return 1;
}
int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%d\n",&n);
    nrt=0;
    for (i=1; i<=n; i++) scanf("%lf %lf\n",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    for (i=1; i<=n-2; i++) for (j=i+1; j<=n-1; j++)
        {
            d=sqrt(1.0*(a[j].x-a[i].x)*(a[j].x-a[i].x)+1.0*(a[j].y-a[i].y)*(a[j].y-a[i].y));
            Sin=(a[j].y-a[i].y)/d;
            Cos=(a[j].x-a[i].x)/d;
            x1=(0.5*Cos-rad3/2*Sin)*d+a[i].x;
            y3=(0.5*Sin+rad3/2*Cos)*d+a[i].y;
            x2=(rad3/2*Sin+0.5*Cos)*d+a[i].x;
            y4=(0.5*Sin-rad3/2*Cos)*d+a[i].y;
            if (cautare_binara(x1,y3,j)!=-1) nrt++;
            if (cautare_binara(x2,y4,j)!=-1) nrt++;
        }
    printf("%d",nrt);
    return 0;
}