F. Mirror
题意
链接 https://codeforces.com/gym/101968/problem/F
三维几何镜像问题:
有 n 个人在 y=0 的平面上(及 xoz 平面).z=0 平面上有一面镜子(边平行于坐标轴).z=a 平面上有 q 个点(保证 a 大于所有人的 z 坐标). 所有人面朝镜子, 且在镜子和 q 个点之间(即每个人的 z 坐标保证 0<z<a).
问对于某个点, 让所有人能够通过镜子看到那个点的镜子的最小面积.
题解
首先考虑镜面, 我们可以通过 (初中科学的) 镜面反射原理, 关于 z=0 做出 z=a 的对称平面 z=-a. 问题就变成了 n 个人看 z=-a 上的某个点.(下图绿点是人, 红点是询问点)
然后观察, 镜子的高和宽是独立的. 于是我们分别求它们的最大值即可.
求高比较简单, 我们朝 - x 方向看 yoz 平面. 通过把每个人跟点 Q 的像 Q'相连, 我们发现离 Q'z 轴距离最近的人对应着镜子的下边界, 最远的人对应着上边界, 通过维护所有人 z 坐标的 max_z&min_z 以及相似三角形可以直接求出两个边界, 复杂度为 O(1).
我们用同样的方法, 朝 - y 方向看 xoz 平面. 通过把每个人跟点 Q 的像 Q'相连, 我们发现, 左右边界并不对应着最左边与最右边的人. 而且随着询问点的变化, 对应着左右边界的人也在变化.
如果我们暴力的找对应左右边界的人, 复杂度为 n*q , 不可行.
我们发现, 对应着左右边界的人虽然随着询问点变化, 但他们都在凸包上(如下图).
更进一步, 如果我们将询问点按照 x 坐标排序, 随着询问的 x 坐标增加, 左右边界的人在凸包上的变化是顺时针旋转的.(考虑你从左到右观察一个正前方的凸包)
于是我们就能够通过一个 nlogn 的凸包预处理然后 O(1)地回答每个询问, 复杂度为 O(q+nlogn)
剩下的是实现 "从左到右看凸包时凸包左右边界的顺时针更新".
首先是写 out,in 函数(右手法则, 向外转就是逆时针), 用来逆时针, 顺时针遍历凸包上的点. 因为极角排序凸包存的点是逆时针的(极角排序的那个角是与 y 轴的逆时针夹角.), 所以 out 就是 ++.
先找到凸包的下上顶点, 作为初始的左右边界的对应点.
然后根据 x 坐标从小到大枚举询问点 Q.
对于每个 Q, 不断顺时针更新左边界对应的人, 直到他与 Q 的连线在他凸包上顺时针的下一个人与 Q 的连线的外面(直观上显然正确). 右边界同理.
某些编辑器比如 codeforces 不能混用 iostream 与 stdio
代码
- #include<cmath>
- #include<algorithm>
- #include<iostream>
- #include<stdio.h>
- #include<map>
- #include<string.h>
- #include<queue>
- #include<stack>
- using namespace std;
- #define debug(x) cerr<<#x<<"="<<(x)<<endl
- #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
- #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
- //#define double long long
- typedef long long ll;
- typedef double db;
- const int maxn = 2e5 + 5;
- const db eps = 1e-7;
- int n, q, a;
- long double ans[maxn];
- bool eq(double a, double b) { return abs(a - b) <= eps; }
- struct V {
- double x, y;
- V(double a = 0.0, double b = 0.0) :x(a), y(b) {}
- void sc() { scanf("%lf%lf", &x, &y); }
- double operator |(V const &o)const {
- return x * o.y - o.x * y;
- }
- bool operator <(V const &o)const {
- if (eq(x, o.x))return y <o.y;
- return x < o.x;
- }
- V operator -(V const &o)const { return V(x - o.x, y - o.y); }
- void pr() { printf("%lf %lf\n", x, y); }
- }st[maxn];
- pair<V, int> Q[maxn];
- bool cmpr(V const &a, V const &b) {
- V v1 = a - st[0], v2 = b - st[0];
- return (v1 | v2) <-eps;
- }
- vector<V> ch;
- void getCH() {
- sort(st + 1, st + n, cmpr);
- ch.push_back(st[0]);
- rep(i, 1, n-1) {
- while (ch.size()> 1 && (st[i] - ch.back() | ch.back() - ch[ch.size() - 2]) <eps)ch.pop_back();
- ch.push_back(st[i]);
- }
- }
- int out(int x) { return x ? x - 1 : ch.size() - 1; }
- int in(int x) { return x + 1 == (int)ch.size() ? 0 : x + 1; }
- double getx(double xs, double z, double xq) {
- return xs + z / (z + a) * (xq - xs);
- }
- int main() {
- //FAST_IO;
- int t;
- cin>> t;
- while (t--) {
- cin>> n>> a;
- rep(i, 0, n - 1)st[i].sc();
- db zmn = st[0].y, zmx = st[0].y;
- rep(i, 0, n - 1) {
- zmn = min(zmn, st[i].y);
- zmx = max(zmx, st[i].y);
- }
- rep(i, 0, n - 1)st[i].y = a - st[i].y;
- sort(st, st + n);
- ch.clear();
- getCH();
- cin>> q;
- ll qx = 0, qy = 0;
- rep(i, 1, q) {
- Q[i].first.sc();
- Q[i].second = i;
- }
- sort(Q + 1, Q + 1 + q);
- int lp = 0, rp = 0;
- rep(i, 0, ch.size() - 1)ch[i].y = a - ch[i].y;
- while (ch[in(rp)].y <ch[rp].y)rp = in(rp);
- while (ch[out(lp)].y> ch[lp].y)lp = out(lp);
- rep(i, 1, q) {
- while (true) {
- int ni = in(lp);
- if (getx(ch[ni].x, ch[ni].y, Q[i].first.x) <getx(ch[lp].x, ch[lp].y, Q[i].first.x))lp = ni;
- else break;
- }
- while (true) {
- int ni = in(rp);
- if (getx(ch[ni].x, ch[ni].y, Q[i].first.x)> getx(ch[rp].x, ch[rp].y, Q[i].first.x))rp = ni;
- else break;
- }
- double x = abs(getx(ch[rp].x, ch[rp].y, Q[i].first.x) - getx(ch[lp].x, ch[lp].y, Q[i].first.x));
- double h = getx(0, zmx, Q[i].first.y) - getx(0, zmn, Q[i].first.y);
- ans[Q[i].second] = (long double)x * h;
- //printf("%.20lf\n", x*h);
- }
- rep(i, 1, q)printf("%.20lf\n", (double)ans[i]);
- }
- cin>> n;
- }
- /*
- 1
- 3 3
- -2 1
- 7 2
- 3 1
- 3
- 2 5
- -2 4
- 8 10
- */
心路历程
当有两个以上的 bug 时你就炸了
wa0:FAST_IO codeforces 以用就 wa
wa1: 输出 rep(i,1,q) not rep(i,1,n)// 最后才发现
wa2: 凸包板子里面下标从 0 开始.
来源: http://www.bubuko.com/infodetail-3015792.html