首页 > 代码库 > uva 1511 - Soju(贪心)
uva 1511 - Soju(贪心)
题目链接:uva 1511 - Soju
题目大意:给出两个点集,问说分别从两个点集中取一点的哈夫曼距离最小值。注意一个点集的x坐标小于0,另一个大于0.
解题思路:因为x2一定大于x1,所以对于x这一维,一定是+x2-x1,所以只需要考虑y这一维坐标即可。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
struct point {
int x, y, flag;
}p[maxn*2];
int N, M;
bool cmp (const point& a, const point& b) {
return a.y < b.y;
}
void init () {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d%d", &p[i].x, &p[i].y);
p[i].flag = 0;
}
scanf("%d", &M);
for (int i = 0; i < M; i++) {
scanf("%d%d", &p[i+N].x, &p[i+N].y);
p[i+N].flag = 1;
}
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
int ans = INF, now = INF;
sort(p, p + N + M, cmp);
for (int i = 0; i < N + M; i++) {
if (p[i].flag)
now = min(now, p[i].x - p[i].y);
else
ans = min(ans, now - p[i].x + p[i].y);
}
now = INF;
reverse(p, p + N + M);
for (int i = 0; i < N + M; i++) {
if (p[i].flag)
now = min(now, p[i].x + p[i].y);
else
ans = min(ans, now - p[i].x - p[i].y);
}
printf("%d\n", ans);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。