LEM - RIVER

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define sqr(x) ((x)*(x))
const int N = 1111;
using namespace std;
struct P {
    int x; int y;
};
P a[N], b[N];
double height(P a, P b, P c) {
    double S = abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
    double AC2 = sqr(a.x-c.x)+sqr(a.y-c.y);
    double AB2 = sqr(a.x-b.x)+sqr(a.y-b.y);
    double BC2 = sqr(b.x-c.x)+sqr(b.y-c.y);
    if (AB2 > AC2 + BC2) return sqrt(AC2);
    if (AC2 > AB2 + BC2) return sqrt(AB2);
    return S / (sqrt(BC2));
}

int main()
{
    //freopen("LEM.in", "r", stdin);
    int n, m, i, j; double res = 1e9;
    scanf("%d %d\n", &n, &m);
    for(i=1; i<=n; i++) scanf("%d %d\n", &a[i].x, &a[i].y);
    for(i=1; i<=m; i++) scanf("%d %d\n", &b[i].x, &b[i].y);
    for(i=1; i<=n; i++)
        for(j=1; j<m; j++)
            res = min(res, height(a[i], b[j], b[j+1]));
    for(j=1; j<=m; j++)
        for(i=1; i<n; i++)
            res = min(res, height(b[j], a[i], a[i+1]));
    printf("%.3f", res);
    return 0;
}

Download