题目描述

Two kittens, Max and Min, play with a pair of non-negative integers $x$ and $y$. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, $x$ and $y$ became negative at the same time, and kitten Max tries to prevent him from doing so.
Each kitten has a set of pairs of integers available to it. Kitten Max has $n$ pairs of non-negative integers $(a_i, b_i)$, and kitten Min has $m$ pairs of non-negative integers $(c_j, d_j)$. As kitten Max makes a move, it can take any available pair $(a_i, b_i)$ and add $a_i$ to $x$ and $b_i$ to $y$, and kitten Min can take any available pair $(c_j, d_j)$ and subtract $c_j$ from $x$ and $d_j$ from $y$. Each kitten can use each pair multiple times during distinct moves.
Max moves first. Kitten Min is winning if at some moment both numbers $a, b$ are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.

算法分析

\begin{align} &\exists (a, b), \; a, b \ge 0 \land a+b \gt 0, \\ &\exists (a_i, b_i), \; \forall (c_j, d_j), \; ((a_i, b_i), (a, b)) \ge ((c_j, d_j), (a, b)) \end{align}

$\because$初始时$((x, y), (a, b))=ax+by \gt 0$
$((a_i-c_j, b_i-d_j), (a, b))=((a_i, b_i), (a, b))-((c_j, d_j), (a, b)) \ge 0$
$\therefore$在任意时刻$((x’, y’), (a, b)) \gt 0$
$\therefore x’, y’$不全为负数

$$\exists (c_j, d_j), \; (a_i, b_i) \parallel (c_j, d_j) \land |(a_i, b_i)| \lt |(c_j, d_j)|$$

代码

#include <vector>
#include <cstdio>
#include <algorithm>

#define int long long

typedef const int ci;

inline int max(ci &a, ci &b) {
return a > b ? a : b;
}

static ci N = 100005;
int st[N << 1];
std :: vector <int> rec;
struct Point {
int type, x, y;
Point(ci &_x = 0, ci &_y = 0) : type(0), x(_x), y(_y) {}
bool operator == (const Point &p) const {
return type == p.type && x == p.x && y == p.y;
}
bool operator < (const Point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
Point operator - (const Point &p) const {
return Point(x - p.x, y - p.y);
}
int operator * (const Point &p) const {
return x * p.y - y * p.x;
}
} p[N << 1];

signed main() {
int n, m, tot, mxa = 0, mxb = 0; scanf("%lld%lld%*d%*d", &n, &m), tot = n + m + 3;
for (int i = 0; i < n; ++ i) scanf("%lld%lld", &p[i].x, &p[i].y), p[i].type = 1;
for (int i = n; i < n + m; ++ i) scanf("%lld%lld", &p[i].x, &p[i].y), p[i].type = 2, mxa = max(mxa, p[i].x), mxb = max(mxb, p[i].y);
p[n + m] = Point(0, 0), p[n + m + 1] = Point(mxa, 0), p[n + m + 2] = Point(0, mxb), std :: sort(p, p + tot);
for (int i = 0, j; i < tot; i = j) {
j = i; int rec = 0;
while (j < tot && p[i].x == p[j].x && p[i].y == p[j].y) ++ j;
for (int k = i; k < j; ++ k) rec |= p[k].type;
if (rec & 1) for (int k = i; k < j; ++ k) p[k].type = 1;
}
tot = std :: unique(p, p + tot) - p;
int sz = 0;
for (int i = 0; i < tot; ++ i) {
while (sz > 1 && (p[st[sz - 1]] - p[st[sz - 2]]) * (p[i] - p[st[sz - 1]]) < 0) -- sz;
st[sz ++] = i;
}
for (int i = 0; i < sz; ++ i) rec.push_back(st[i]); sz = 0;
for (int i = tot - 1; ~ i; -- i) {
while (sz > 1 && (p[st[sz - 1]] - p[st[sz - 2]]) * (p[i] - p[st[sz - 1]]) < 0) -- sz;
st[sz ++] = i;
}
for (int i = 1; i < sz - 1; ++ i) rec.push_back(st[i]);
for (int i = rec.size() - 1; ~ i; -- i) if (p[rec[i]].type == 1) return printf("Max\n"), 0;
return printf("Min\n"), 0;
}


题目描述

Bessie, Farmer John’s prize cow, has just won first place in a bovine beauty contest, earning the title ‘Miss Cow World’. As a result, Bessie will make a tour of $N$ farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates $(x, y)$, each having a value in the range $-10000 \ldots 10000$. No two farms share the same pair of coordinates.
Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring. Help Bessie by computing the maximum distance among all pairs of farms.

代码

#include <cstdio>
#include <algorithm>

int max(int a, int b) {
return a > b ? a : b;
}

static const int N = 50005;
int st[N], rec[N];
struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
bool operator < (const Point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
Point operator - (const Point &p) const {
return Point(x - p.x, y - p.y);
}
int operator * (const Point &p) const {
return x * p.y - y * p.x;
}
int operator ! () const {
return x * x + y * y;
}
} p[N];

int main() {
int n; scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf("%d%d", &p[i].x, &p[i].y);
int top = 0, tot = 0; std :: sort(p, p + n);
for (int i = 0; i < n; ++ i) {
while (top > 1 && (p[st[top - 1]] - p[st[top - 2]]) * (p[i] - p[st[top - 2]]) <= 0) -- top;
st[top ++] = i;
}
for (int i = 0; i < top; ++ i) rec[tot ++] = st[i];
top = 0;
for (int i = n - 1; ~ i; -- i) {
while (top > 1 && (p[st[top - 1]] - p[st[top - 2]]) * (p[i] - p[st[top - 2]]) <= 0) -- top;
st[top ++] = i;
}
for (int i = 1; i < top - 1; ++ i) rec[tot ++] = st[i];
int mx = 0, pnt = 1;
for (int i = 0; i < tot; ++ i) {
int nxt = (i + 1) % tot; Point cur = p[rec[nxt]] - p[rec[i]];
while (cur * (p[rec[pnt]] - p[rec[i]]) < cur * (p[rec[(pnt + 1) % tot]] - p[rec[i]])) (++ pnt) %= tot;
mx = max(mx, max(! (p[rec[pnt]] - p[rec[i]]), ! (p[rec[pnt]] - p[rec[nxt]])));
}
printf("%d\n", mx);
return 0;
}


题目描述

The old King decided to divide the Kingdom into parts among his three sons. Each part is a polygonal area. Taking into account the bad temper of the middle son the King gave him a part of Kingdom such that moving straight from any place of this part to any other place of this part he will not cross the boundary.
There are several mineral deposits in the Kingdom. Each mineral deposit looks like a straight line segment. The middle son wants to know what part of mineral deposits is located inside his territory (not including the boundaries).

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) { return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1; }

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {};
bool operator < (const Point &p) const { return ! cmp(x, p.x) ? cmp(y, p.y) == -1 : cmp(x, p.x) == -1; }
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &a) const { return Point(x * a, y * a); }
Point operator / (const double &a) const { return Point(x / a, y / a); }
double operator * (const Point &p) const { return x * p.y - y * p.x; }
double operator ! () const { return sqrt(x * x + y * y); }
};

struct Line {
Point a, b;
Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
bool operator | (const Line &l) const { return ! cmp((b - a) * (l.b - l.a), 0); }
Point operator & (const Line &l) const {
double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
return a + (b - a) * t;
}
};

struct Solver {
private:
static const int N = 410;
int n, q, top;
Point point[N], sta[N];
vector <Point> poly;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
scanf("%d", &q);
}
void init() {
sort(point + 1, point + n + 1);
for (int i = 1; i <= n; ++ i) {
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 1; i <= top; ++ i) poly.push_back(sta[i]); top = 0;
for (int i = n; i; -- i){
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 2; i < top; ++ i) poly.push_back(sta[i]);
}
bool in(Point p) {
for (int i = 0; i < poly.size(); ++ i)
if (cmp((poly[(i + 1) % poly.size()] - poly[i]) * (p - poly[i]), 0) < 0) return false;
return true;
}
void process() {
Line l;
scanf("%lf%lf%lf%lf", &l.a.x, &l.a.y, &l.b.x, &l.b.y);
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
vector <Point> inter;
for (int i = 0; i < poly.size(); ++ i)
if (! (Line(poly[i], poly[(i + 1) % poly.size()]) | l)) {
Line tmp = Line(poly[i], poly[(i + 1) % poly.size()]);
Point p = tmp & l;
if ((cmp(p.x, l.a.x) || cmp(p.y, l.a.y)) && (cmp(p.x, l.b.x) || cmp(p.y, l.b.y)) && cmp(min(l.a.x, l.b.x), p.x) < 1 && cmp(p.x, max(l.a.x, l.b.x)) < 1 && cmp(min(l.a.y, l.b.y), p.y) < 1 && cmp(p.y, max(l.a.y, l.b.y)) < 1 && cmp(min(tmp.a.x, tmp.b.x), p.x) < 1 && cmp(p.x, max(tmp.a.x, tmp.b.x)) < 1 && cmp(min(tmp.a.y, tmp.b.y), p.y) < 1 && cmp(p.y, max(tmp.a.y, tmp.b.y)) < 1) {
for (int j = 0; j < inter.size(); ++ j) if (! cmp(inter[j].x, p.x) && ! cmp(inter[j].y, p.y)) goto label;
inter.push_back(p);
}
label: ;
}
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
if (inter.empty())
if (in(l.a) && in(l.b)) printf("%.2lf\n", ! (l.b - l.a));
else printf("0.00\n");
else if (inter.size() == 2) printf("%.2lf\n", ! (inter[1] - inter[0]));
else if (in(l.a)) printf("%.2lf\n", ! (inter[0] - l.a));
else if (in(l.b)) printf("%.2lf\n", ! (inter[0] - l.b));
else printf("0.00\n");
}

public:
void solve() { input(), init(); while (q --) process(); }
} solver;

int main() {
solver.solve();
return 0;
}