Cod sursa(job #209334)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 21 septembrie 2008 20:47:25
Problema Cast Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

long x[310], y[310], n, i, j, k, l, k1, k2;
long double a, d, p, x1[310], x2[310], m;

int main()
{
    freopen("geom.in","r",stdin);
    freopen("geom.out","w",stdout);
    scanf("%ld %ld", &n, &k);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d", &x[i], &y[i]);
    }
    m=-1;
    for(i=1; i<=n-1; i++)
    {
        for(j=i+1; j<=n; j++)
        {
            k1=0;
            k2=0;
            d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            for(l=1; l<=n; l++)
            {
                a=x[i]*y[j]-x[j]*y[i]+x[j]*y[l]-x[l]*y[j]+x[l]*y[i]-x[i]*y[l];
                p=a/d;
                if (p>=0) 
                {
                    k1++;
                    x1[k1]=p;
                }
                if (p<=0)
                {
                    k2++;
                    x2[k2]=-p;
                }
            }
            sort(x1+1,x1+k1+1);
            sort(x2+1,x2+k2+1);
            if (k<=k1){ if((m==-1)||(x1[k]<m)) m=x1[k];}
            if (k<=k2){ if((m==-1)||(x2[k]<m)) m=x2[k];}
        }
    }
    printf("%.3Lf\n", m);
    return 0;
}