Cod sursa(job #1677203)

Utilizator ASTELOTudor Enescu ASTELO Data 6 aprilie 2016 13:37:28
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct eu{double x,y;
long long x1,y1;};
eu v[1501],m,p1,p2;
long long n,i,j,k,nr,hh1,l1,l2;
double l,hh;
bool sorting(eu a,eu b)
    {
    if(a.x1<b.x1||a.x1==b.x1&&a.y1<b.y1)
        return 1;
    return 0;
    }
int main ()
{
freopen("triang.in","r",stdin);
freopen("triang.out","w",stdout);
scanf("%lld",&n);
hh=sqrt(3);
for(i=1;i<=n;i++)
    {
    scanf("%lf%lf",&v[i].x,&v[i].y);
    v[i].x1=v[i].x*1000;
    v[i].y1=v[i].y*1000;
    }
sort(v+1,v+n+1,sorting);
hh1=hh*1000;
for(i=1;i<n-1;i++)
    for(j=i+1;j<=n-1;j++)
        {
        m.x1=(v[i].x+v[j].x1)/2;
        m.y1=(v[i].y1+v[j].y1)/2;
        l=sqrt((v[i].y-v[j].y)*(v[i].y-v[j].y)+(v[i].x-v[j].x)*(v[i].x-v[j].x));
        l1=l*1000;
        double panta;
        if(v[i].y==v[j].y)
            {
            p1.x1=m.x1;
            p1.y1=m.y1+l1*hh1/2;
            p2.x1=m.x1;
            p2.y1=m.y1-l1*hh1/2;
            }
        else
            {
            panta=(v[i].x-v[j].x)/(v[i].y-v[j].y);
            panta=(-1)/panta;
            double a,b;
            long long panta1,b1,a1;
            panta1=1000*panta;
            b=sqrt(3*l*l/(4*(panta*panta+1)));
            b1=1000*b;
            a1=b1*panta1/1000;
            p1.x1=m.x1+a1;
            p1.y1=m.y1+b1;
            p2.x1=m.x1-a1;
            p2.y1=m.y1-b1;
            }
        long long l1=j+1,l2=n,mid,o=0;
        while(l1<=l2)
            {
            mid=(l1+l2)/2;
            if(abs(v[mid].x1-p1.x1)<=1&&abs(v[mid].y1-p1.y1)<=1)
                {
                o=mid;
                break;
                }
            if(v[mid].x1<p1.x1||v[mid].x1==p1.x&&v[mid].y1<p1.y1)
                l1=mid+1;
            else
                l2=mid-1;
            }
        if(o!=0)
            nr++;
        l1=j+1;
        l2=n;
        o=0;
        while(l1<=l2)
            {
            mid=(l1+l2)/2;
            if(abs(v[mid].x1-p2.x1)<=1&&abs(v[mid].y1-p2.y1)<=1)
                {
                o=mid;
                break;
                }
            if(v[mid].x1<p2.x1||v[mid].x1==p2.x1&&v[mid].y1<p2.y1)
                l1=mid+1;
            else
                l2=mid-1;
            }
        if(o!=0)
            nr++;
        }
printf("%d",nr);
return 0;
}