Max and Min

题目描述

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.

题意概述

有两个人Max和Min,初始时有两个数$x$和$y$。Max有$n$个数对$(a_i, b_i)$,Min有$m$个数对$(c_j, d_j)$。两个人轮流操作,Max先手。Max可以选择一个数对$(a_i, b_i)$,将$x$加上$a_i$、$y$加上$b_i$;Min可以选择一个数对$(c_j, d_j)$,将$x$减去$c_j$、$y$减去$d_j$。若在某一时刻$x, y$同时为负,则Min获胜,否则Max获胜。求谁必胜。
数据范围:$1 \le n, m \le 10^5, \; 1 \le x, y, a_i, b_i, c_j, d_j \le 10^9$。

算法分析

对于两个向量$v_1, v_2$,我们用$(v_1, v_2)$表示$v_1 \cdot v_2$。
我们把所有数对看成从原点出发的向量。假设有一个新的向量$(a, b)$。若
$$
\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}
$$
那么Max必胜。证明如下:

$\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_0}, d_{j_0}), (c_{j_1}, d_{j_1})$,点$(a_i, b_i)$严格在点$(c_{j_0}, d_{j_0})$、$(c_{j_1}, d_{j_1})$和原点所组成的三角形内部,那么根据上述证明,$(a_i, b_i)$对Max没有贡献。特别的,若
$$\exists (c_j, d_j), \; (a_i, b_i) \parallel (c_j, d_j) \land |(a_i, b_i)| \lt |(c_j, d_j)|$$
那么$(a_i, b_i)$也没有贡献。
算法已经很清晰了——对Min的向量求凸包,判断是否所有Max的向量都严格在凸包内部。假设Min的向量中$c_j$的最大值为$mx_c$,$d_j$的最大值为$mx_d$,凸包中还需加入三个点$(0, 0), (mx_c, 0), (0, mx_d)$。
具体实现时,可以将Max的向量拿来一起求凸包。若求出来的凸包上有Max的向量,则Max必胜,否则Min必胜。

代码

#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;
}

Beauty Contest

题目描述

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.

题意概述

求$N$个点中最远点对之间的距离。
数据范围:$2 \le N \le 50000$。

算法分析

显然最远点对一定在凸包上,因此可以先计算出凸包。接着考虑旋转卡壳。被一对卡壳正好卡住的点对互为对踵点,那么最远点对一定互为对踵点。只要将卡壳绕凸包旋转一周,就可以找到所有对踵点对,取其中距离最远的点对即可。

代码

#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;
}

Inheritance

题目描述

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).

题意概述

给定一个凸$N$边形,求一条线段在它内部的长度(不包括边界)。
数据范围:$3 \le N \le 400$。

算法分析

由于点的顺序是随机的,因此需要先求凸包,接着计算线段与凸包的交点,根据交点个数来分类讨论。
此题细节很多,需要考虑线段与某条边共线、线段顶点在某条边上、线段经过某个顶点等情况。

代码

#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;
}