Problem:Central Avenue Road 感觉第一次写的比较清晰的判断点线关系。

题意:给出一些整数点,然后求某两点的连线,使得左右两边的点数量相差小于1并且要求这条线最短。

根据y = kx + b 推 ax + by + c = 0,这两个直线方程,进而带入点判断正负来判断在直线的上/下(左/右)。

# include <cstdio>
# include <algorithm>
# include <cmath>
# define rep(x) for ( x = 1; x <= n; ++x )
using namespace std;
int x[107], y[107];
int n;

double ans;
inline double sqr(double x)
{ return x * x; }
inline double dis(int a, int b)
{
    double sum = sqr((double)(x[a] - x[b])) + sqr((double)(y[a] - y[b]));
    return sqrt(sum);
}
void test(int a, int b)
{
    int i, j;
    int l = 0, r = 0;
    double K, B;
    if ( x[a] == x[b] && y[a] == y[b] ) return;
    if ( x[a] == x[b] )
    {
        rep(i)
            if ( x[i] < x[a] ) l++;
            else if ( x[i] > x[a] ) r++;
    }
    else if ( y[a] == y[b] )
    {
        rep(i)
            if ( y[i] < y[a] ) l++;
            else if ( y[i] > y[a] ) r++;
    }
    else
    {
        K = (y[a] - y[b]) / ( x[a] - x[b] );
        B = y[a] - K * x[a];
        rep(i)
            if ( i == a || i == b ) continue;
            else
            {
                double tmp = K * x[i] - y[i] + B;
                if ( tmp > 0 ) l++;
                else if ( tmp < 0) r++;
            }
    }
    if ( abs(l-r) < 2 )
    {
        double d = dis(a, b);
        if ( d < ans ) ans = d;
    }
}
int main()
{
    int i, j;
    while ( scanf("%d", &n), n )
    {
        ans = 9999999.99;
        rep(i) scanf("%d%d", &x[i], &y[i]);
        rep(i)
            for ( j = i + 1; j <= n; ++j )
                test(i, j);
        if ( n == 1 ) ans = 0.0;
        printf("%.3f\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>