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

Meeting

题目描述

Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between $X$ o’clock and $Y$ o’clock. Because they never get anywhere on time (they were late even on the day of the regional contest), they did not set an exact time when they will meet. However, they decided that the one who gets first at the meeting point will not wait more than $Z$ minutes for the other one (they calculated that, if the other one will not come within $Z$ minutes from the arrival of the first of them, then it is very probable that he will not show up at all).
Knowing that, in the end, both of them will show up at some time between $X$ o’clock and $Y$ o’clock (not necessarily after an integer number of minutes), compute which is the probability that they will actually meet.

题意概述

给定整数$X, Y$和实数$Z$,在$X$时到$Y$时之间任选两个时刻,求时刻之差不超过$Z$分钟的概率。
数据范围:$0 \le X \lt Y \le 24, \; 0 \lt Z \le 60(Y-X)$。

算法分析

在平面直角坐标系内以第一个时刻为$x$轴、第二个时刻满足要求的概率为$y$轴画出一个封闭图形,那么答案就是这个图形的面积除以$X$时与$Y$时之差。分两种情况讨论:$2Z \le 60(Y-X)$和$2Z \gt 60(Y-X)$。两种情况得到的封闭图形均为一个${Z \over 60(Y-X)} \times 60(Y-X)$的矩形加上一个下底长$60(Y-X)$的梯形(上底可为$0$)。前者上底加下底为$2(60(Y-X)-Z)$,高为${Z \over 60(Y-X)}$;后者上底加下底为$2Z$,高为$(1-{Z \over 60(Y-X)})$。

代码

#include <cstdio>

using namespace std;

struct Solver {
private:
  int x, y; double z;
  void input() { scanf(" %d %d %lf", &x, &y, &z); }
  void process() {
    int all = (y - x) * 60;
    double sum = 0;
    if (2 * z <= all) sum = z + 2 * (all - z) * (z / all) / 2;
    else sum = z + 2 * z * (1 - z / all) / 2;
    printf("%.8lf\n", sum / all);
  }

public:
  void solve() { input(), process(); }
} solver;

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

Erasing Edges

题目描述

Little Johnny painted on a sheet of paper a polygon with $N$ vertices. Then, for every edge of the polygon, he drew the middle point of the edge. After that, he went to school. When he came back, he found out that his brother had erased the polygon (both the edges and the vertices). The only thing left were the middle points of the edges of the polygon. Help Johnny redraw his polygon.

题意概述

给定一个$N$边形各边的中点,还原这个$N$边形。边可以相交。
数据范围:$3 \le N \le 10000$。

算法分析

设$N$边形第$i$个点的坐标为$(x_i, y_i)$,第$i$条边中点的坐标为$(x_i’, y_i’)$,可以得到以下方程
$$
\left\{
\begin{array}{c}
x_1+x_2=2x_1′ \\
x_2+x_3=2x_2′ \\
\cdots \\
x_N+x_1=2x_N’
\end{array}
\right.
$$
对$y$同理。当$N$为奇数时,方程有唯一解,解出即可;当$N$为偶数时,方程无解或有无数解,只需尝试构造一组解并判断是否合法。

代码

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

#define random (1.0 * rand() / RAND_MAX)

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) {}
  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 &n) const { return Point(x * n, y * n); }
  Point operator / (const double &n) const { return *this * (1 / n); }
  Point operator | (const Point &p) const { return *this + (p - *this) * 2; }
};

struct Solver {
private:
  static const int N = 10010;
  int n;
  Point point[N];
  vector <Point> ans;
  void input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
  }
  void process() {
    Point p;
    if (n & 1) {
      double sum = 0;
      for (int i = 1; i <= n; ++ i) sum += point[i].x;
      for (int i = 2; i <= n; i += 2) sum -= point[i].x * 2;
      p.x = sum, sum = 0;
      for (int i = 1; i <= n; ++ i) sum += point[i].y;
      for (int i = 2; i <= n; i += 2) sum -= point[i].y * 2;
      p.y = sum;
    } else p = Point(random * 100000, random * 100000);
    for (int i = 1; i <= n; ++ i) ans.push_back(p), p = p | point[i];
    if (cmp(p.x, ans[0].x) || cmp(p.y, ans[0].y)) printf("NO\n");
    else {
      printf("YES\n");
      for (int i = 0; i < ans.size(); ++ i) printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
    }
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  srand(47), solver.solve();
  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;
}

Broken Line

题目描述

There is a closed broken line on a plane with sides parallel to coordinate axes, without self-crossings and self-contacts. The broken line consists of $K$ segments. You have to determine, whether a given point with coordinates $(X_0, Y_0)$ is inside this closed broken line, outside or belongs to the broken line.

题意概述

给定一个简单$N$边形,它的每条边都平行于坐标轴。问点$(X_0, Y_0)$是否在多边形内。
数据范围:$4 \le N \le 10000$。

算法分析

从$(X_0, Y_0)$向右水平射出一条射线,若射线与$N$边形有奇数个交点则该点在多边形内。
判断一条边是否与射线相交就是要看该边的两个端点是否在射线异侧,在射线上或射线上方算同一侧,在射线下方算另一侧。

代码

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

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Line { int x1, y1, x2, y2; };

struct Solver {
private:
  static const int K = 10010;
  int k, x, y;
  Line l[K];
  void input() {
    io > k;
    for (int i = 1; i <= k; ++ i) {
      io > l[i].x1 > l[i].y1 > l[i].x2 > l[i].y2;
      if (l[i].x1 > l[i].x2 || l[i].y1 > l[i].y2) swap(l[i].x1, l[i].x2), swap(l[i].y1, l[i].y2);
    }
    io > x > y;
  }
  bool in(int x, int y, Line l) {
    if (l.x1 == l.x2) return x == l.x1 && l.y1 <= y && y <= l.y2;
    else return y == l.y1 && l.x1 <= x && x <= l.x2;
  }
  void process() {
    for (int i = 1; i <= k; ++ i) if (in(x, y, l[i])) { io < (char *) "BORDER\n"; return; }
    int cnt = 0;
    for (int i = 1; i <= k; ++ i)
      cnt += l[i].x1 == l[i].x2 && l[i].x1 > x && ((l[i].y1 <= y) ^ (l[i].y2 <= y));
    if (cnt & 1) io < (char *) "INSIDE\n"; else io < (char *) "OUTSIDE\n";
  }

public:
  void solve() { input(), process(); }
} solver;

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

Archipelago

题目描述

Archipelago Ber-Islands consists of $N$ islands that are vertices of equiangular and equilateral $N$-gon. Islands are clockwise numerated. Coordinates of island $N_1$ are $(x_1, y_1)$, and island $N_2$ – $(x_2, y_2)$. Your task is to find coordinates of all $N$ islands.

题意概述

平面上有一个正$N$边形,它的顶点按顺时针方向依次标号。给定第$N_1$、$N_2$个点的坐标$(x_1, y_1)$、$(x_2, y_2)$,求所有顶点的坐标。
数据范围:$3 \le N \le 150, \; N_1 \neq N_2, \; |x_1|, |y_1|, |x_2|, |y_2| \le 2 \times 10^6$。

算法分析

可以先计算出圆心角,根据圆心角、三角函数和向量旋转计算出圆心坐标,之后就可以用向量旋转计算出所有顶点的坐标。
将$(x, y)$绕原点逆时针旋转$\theta$度得到$(x\cos(\theta)-y\sin(\theta), x\sin(\theta)+y\cos(\theta))$。

代码

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

using namespace std;

static const double PI = acos(-1);
static const double EPS = 1e-8;
int cmp(double t) { return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1; }

struct Point {
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  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 { return sqrt(x * x + y * y); }
  double operator & (const Point &p) const { return x * p.x + y * p.y; }
  double operator * (const Point &p) const { return x * p.y - y * p.x; }
  Point operator << (const double &a) const { return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
};

struct Solver {
private:
  static const int N = 160;
  int n, a, b;
  Point p, q, tmp, ans[N];
  void input() { scanf("%d%d%d%lf%lf%lf%lf", &n, &a, &b, &p.x, &p.y, &q.x, &q.y); }
  void init() {
    if (a > b) swap(a, b), swap(p, q);
    double angle = 2 * PI / n * (b - a);
    if (cmp(PI - angle)) {
      tmp = p + (q - p) / 2 / cos((PI - angle) / 2);
      tmp = (tmp - p << (angle - PI) / 2) + p;
    } else tmp = p + (q - p) / 2;
  }
  void process() {
    for (int i = 1; i <= n; ++ i)
      ans[a] = p, a %= n, ++ a, p = (p - tmp << -2 * PI / n) + tmp;
    for (int i = 1; i <= n; ++ i)
      printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
  }

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

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

Dungeon

题目描述

The mission of space explorers found on planet M the vast dungeon. One of the dungeon halls is fill with the bright spheres. The explorers find out that the light rays reflect from the surface of the spheres according the ordinary law (the incidence angle is equal to the reflectance angle, the incidence ray, the reflected ray and the perpendicular to the sphere surface lay in the one plane). The ancient legend says that if the light ray will reflect from the spheres in the proper order, than the door to the room with very precious ancient knowledge will open. You are not to guess the right sequence; your task is much simpler. You are given the positions and the radii of the spheres, the place where the laser shot was made and the direction of light propagation. And you must find out the sequence in which the light will be reflected from the spheres.

题意概述

空间中有$N$个球,给定一条光线,光线在碰到球之后会发生反射,求光线碰到的前十个球。
数据范围:$1 \le N \le 50$。

算法分析

对每一次分别计算出光线碰到的第一个球,也就是沿光线方向距离最近的球。设球的半径为$r$,球心到光源的距离为$l$,球心到光线的距离为$d$,那么光线到球的距离等于$\sqrt{l^2-d^2}-\sqrt{r^2-d^2}$,其中$d$可以用三维叉积来计算。找到最近的球之后需要更新光源和光线方向,这些都可以用向量运算解决。

代码

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

using namespace std;

static const long double EPS = 1e-10;
int cmp(long double t) { return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1; }

struct Point {
  long double x, y, z;
  Point(long double _x = 0, long double _y = 0, long double _z = 0) : x(_x), y(_y), z(_z) {}
  Point operator + (const Point &a) const { return Point(x + a.x, y + a.y, z + a.z); }
  Point operator - (const Point &a) const { return Point(x - a.x, y - a.y, z - a.z); }
  Point operator * (const long double &a) const { return Point(x * a, y * a, z * a); }
  Point operator / (const long double &a) const { return Point(x / a, y / a, z / a); }
  Point operator * (const Point &a) const { return Point(y * a.z - z * a.y, z * a.x - x * a.z, x * a.y - y * a.x); }
  long double operator & (const Point &a) const { return x * a.x + y * a.y + z * a.z; }
  long double operator ! () const { return sqrt(x * x + y * y + z * z); }
  long double operator ^ (const Point &a) const { return (*this & a) / (! *this * ! a); }
};

struct Line {
  Point a, b;
  Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
  long double operator % (const Point &p) const { return ! ((b - a) * (p - a)) / ! (b - a); }
};

struct Ball { Point p; long double r; };

struct Solver {
private:
  static const int N = 50;
  int n;
  Point a, b;
  Ball ball[N];
  void input() {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> ball[i].p.x >> ball[i].p.y >> ball[i].p.z >> ball[i].r;
    cin >> a.x >> a.y >> a.z >> b.x >> b.y >> b.z;
  }
  void process() {
    int p = -1, last = -1;
    for (int i = 0; i < 11; ++ i) {
      long double dis = 100000; p = -1;
      for (int j = 0; j < n; ++ j)
        if (j != last && ~ cmp((b - a) ^ (ball[j].p - a)) && ~ cmp(ball[j].r - Line(a, b) % ball[j].p)) {
          long double tmp = sqrt(abs(! (ball[j].p - a) * ! (ball[j].p - a) - (Line(a, b) % ball[j].p) * (Line(a, b) % ball[j].p))) - sqrt(abs(ball[j].r * ball[j].r - (Line(a, b) % ball[j].p) * (Line(a, b) % ball[j].p)));
          if (cmp(dis - tmp) == 1) dis = tmp, p = j;
        }
      if (! ~ p || i == 10) break; last = p;
      if (i) cout << ' '; cout << p + 1;
      Point c = a + (b - a) / ! (b - a) * dis;
      Point d = ball[p].p + (c - ball[p].p) / ! (c - ball[p].p) * (! (a - ball[p].p) * ((a - ball[p].p) ^ (c - ball[p].p)));
      b = d * 2 - a, a = c;
    }
    if (~ p) cout << " etc."; cout << endl;
  }

public:
  void solve() { input(), process(); }
} solver;

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

Peter and Snow Blower

题目描述

Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machines. In order to make it work, you need to tie it to some point that it does not cover, and then switch it on. As a result it will go along a circle around this point and will remove all the snow from its path.
Formally, we assume that Peter’s machine is a polygon on a plane. Then, after the machine is switched on, it will make a circle around the point to which Peter tied it (this point lies strictly outside the polygon). That is, each of the points lying within or on the border of the polygon will move along the circular trajectory, with the center of the circle at the point to which Peter tied his machine.
Peter decided to tie his car to point $P$ and now he is wondering what is the area of the region that will be cleared from snow. Help him.

题意概述

在平面直角坐标系内有一个$n$边形,按顺时针给定它的所有顶点。现给定一个点$P$,求$n$边形绕着点$P$旋转一周所能扫到的面积。
数据范围:$3 \le n \le 10^5$。

算法分析

可以发现$n$边形扫过的图形是一个环形(或圆)。也就是说,我们只要分别求出这个图形最大和最小的半径,就可以算出面积。显然,最大的半径就是$n$边形中距离点$P$最远的点到点$P$的距离。最小的半径有两种可能:①距离点$P$最近的点到点$P$的距离;②距离点$P$最近的边到点$P$的距离(要求点$P$在这条边上的投影在这条边上)。可以用向量乘法判断点$P$的投影是否在某条边上,用点到直线距离公式求点$P$到某条边的距离,用两点间距离公式求点$P$到某个点的距离。

代码

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const long double pi = 3.1415926535898;
struct point {
  long double x, y;
} p[100001];
long double x, y, ma, mi = 1e18;
long long n;
long double get_dist(int s) {
  int t = s + 1;
  if (t > n) t = 1;
  if (p[s].x == p[t].x) return abs(p[s].x);
  long double a = (p[t].y - p[s].y) / (p[t].x - p[s].x), b = -1, c = a * p[s].x - p[s].y;
  return abs(c) / sqrt(a * a + b * b);
}
long double check(int s) {
  int t = s + 1;
  if (t > n) t = 1;
  long double x1 = p[s].x, y1 = p[s].y, x2 = p[t].x, y2 = p[t].y;
  long double p = x1 * (x2 - x1) + y1 * (y2 - y1), q = x2 * (x1 - x2) + y2 * (y1 - y2);
  if (p < 0 && q < 0) return get_dist(s) * get_dist(s);
  else if (p >= 0) return x1 * x1 + y1 * y1;
  else return x2 * x2 + y2 * y2;
}
bool in() {
  bool ret = false;
  for (long long i = 1, j = n; i <= n; j = i++)
    if (((p[i].y > y) != (p[j].y > y)) && ((p[i].x - p[j].x) * p[i].y / (p[j].y - p[i].y) + p[i].x) > 0)
      ret = !ret;
  return ret;
}
int main()
{
  cin >> n >> x >> y;
  for (int i = 1; i <= n; ++i) {
    cin >> p[i].x >> p[i].y; p[i].x -= x, p[i].y -= y;
    ma = max(ma, p[i].x * p[i].x + p[i].y * p[i].y);
    if (i > 1) mi = min(mi, check(i - 1));
  }
  mi = min(mi, check(n)); if (in()) mi = 0;
  cout << setprecision(10) << fixed << (ma - mi) * pi << endl;
  return 0;
}