Cod sursa(job #998315)

Utilizator thewildnathNathan Wildenberg thewildnath Data 16 septembrie 2013 19:03:20
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;

typedef struct punct
{
    double x,y;
}punct;

punct v[1502];
int n;

int cmp(punct a,punct b)
{
    if(a.x<b.x)
        return 1;
    if(a.x>b.x)
        return 0;
    if(a.y<b.y)
        return 1;
    return 0;
}

int caut(int s,double x,double y)
{
    int m,d=n;
    while(s<=d)
    {
        m=(s+d)/2;
        if(fabs(x-v[m].x)<0.001&&fabs(y-v[m].y)<0.001)
            return 1;
        if(v[m].x<x)
            s=m+1;
        else
            d=m-1;
    }
    return 0;
}

int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    int i,j,sol=0;
    double a=sqrt(3);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+1+n,cmp);

    for(i=1;i<n-1;++i)
    {
        for(j=i+1;j<n;++j)
        {
            if(caut(j+1 ,(v[i].x+v[j].x)/2+a*(v[i].y-v[j].y)/2 , (v[i].y+v[j].y)/2+a*(v[j].x-v[i].x)/2))
                ++sol;
            if(caut(j+1, (v[i].x+v[j].x)/2+a*(v[j].y-v[i].y)/2 , (v[i].y+v[j].y)/2+a*(v[i].x-v[j].x)/2))
                ++sol;
        }
    }
    printf("%d\n",sol);
    return 0;
}