题解 P5859 【「SWTR-03」Plane Mirrors】
caeious
·
·
题解
upd: 在看了 SF 的文章后修了修格式；另外题解的渲染真的很丑。。。建议点击 “在 Ta 的博客查看”。
Solution
用极角做真的更简单诶。。。
在本题解中，极角的值域默认为 (-\pi,\pi]。
平面镜
设两个端点极角为 \alpha,\ \beta(\alpha < \beta).
$\therefore$ $\beta - \alpha \neq \pi
如果 \beta - \alpha > \pi, 说明平面镜跨过射线 \theta = \pi,就对应两段 [-\pi,\alpha]、[\beta,\pi]。
否则对应一段 [\alpha,\beta]。
射线
显然，若设 (x,y) 极角为 \varphi , 则对应区间 [\varphi,\varphi]。
综上
- opt = 1: 区间 [\alpha',\beta'] 增加 v
- opt = 2: 区间[\alpha',\beta'] 减少 v
- opt = 3: 查询区间 [\alpha',\alpha'] 的 \max
- opt = 4: 查询区间 [\alpha',\beta'] 的 \max
具体实现先将输入中出现的极角集合 S 离散化，再用线段树维护区间加、区间求 \max 就好了。
浮点误差
$\therefore$ $\forall \alpha,\beta \in S(\alpha \neq \beta),$ 有 $|\alpha - \beta| \geq \frac{\pi}{4} - \arctan(1 - 10^{-5}) \approx 5.1 \times 10^{-6}$.
$\therefore$ 离散化角度时取EPS = $10^{-10}$ 足够（其实即使不用EPS也能过qwq)。
## Code
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
const int LEN = 100000;
struct fastio{
int it,len;
char s[LEN + 5];
fastio(){
it = len = 0;
}
char get(){
if(it < len) return s[it++];
it = 0, len = fread(s,1,LEN,stdin);
return len ? s[it++] : EOF;
}
bool notend(){
char c;
for(c = get();c == ' ' || c == '\n';c = get());
if(it) it--;
return c != EOF;
}
void put(char c){
if(it == LEN) fwrite(s,1,LEN,stdout), it = 0;
s[it++] = c;
}
void flush(){
fwrite(s,1,it,stdout);
}
}buff,bufo;
inline int getint(){
char c; int res = 0, sig = 1;
for(c = buff.get();c < '0' || c > '9';c = buff.get()) if(c == '-') sig = -1;
for(;c >= '0' && c <= '9';c = buff.get()) res = res * 10 + (c - '0');
return sig * res;
}
inline ll getll(){
char c; ll res = 0, sig = 1;
for(c = buff.get();c < '0' || c > '9';c = buff.get()) if(c == '-') sig = -1;
for(;c >= '0' && c <= '9';c = buff.get()) res = res * 10 + (c - '0');
return sig * res;
}
inline void putint(int x,char suf){
if(!x) bufo.put('0');
else{
if(x < 0) bufo.put('-'), x = -x;
int k = 0; char s[15];
while(x){
s[++k] = x % 10 + '0';
x /= 10;
}
for(;k;k--) bufo.put(s[k]);
}
bufo.put(suf);
}
inline void putll(ll x,char suf){
if(!x) bufo.put('0');
else{
if(x < 0) bufo.put('-'), x = -x;
int k = 0; char s[25];
while(x){
s[++k] = x % 10 + '0';
x /= 10;
}
for(;k;k--) bufo.put(s[k]);
}
bufo.put(suf);
}
inline char get_char(){
char c;
for(c = buff.get();c == ' ' || c == '\n';c = buff.get());
return c;
}
#define maxn 200005
const double pi = acos(-1);
struct Query{
int opt,x0,y0,x2,y2,v;
// opt = 2: v = d
// opt = 3: (x0,y0) = (x,y)
// opt = 4: v = d
}qs[maxn];
int id[maxn],num;
int n,len;
vector <double> thetas;
struct Sgt{
int maxi[maxn << 3],add[maxn << 3];
void up(int id){
maxi[id] = max(maxi[id << 1],maxi[id << 1 | 1]);
maxi[id] += add[id];
}
void down(int id){
if(add[id]){
maxi[id << 1] += add[id];
add[id << 1] += add[id];
maxi[id << 1 | 1] += add[id];
add[id << 1 | 1] += add[id];
add[id] = 0;
}
}
void _plus(int id,int l,int r,int ql,int qr,int x){
if(ql <= l && r <= qr){
maxi[id] += x;
add[id] += x;
}else{
down(id);
int mid = (l + r) >> 1;
if(ql <= mid) _plus(id << 1,l,mid,ql,qr,x);
if(mid < qr) _plus(id << 1 | 1,mid + 1,r,ql,qr,x);
up(id);
}
}
int query(int id,int l,int r,int ql,int qr){
if(ql <= l && r <= qr) return maxi[id];
down(id);
int mid = (l + r) >> 1, res = 0;
if(ql <= mid) res = max(res,query(id << 1,l,mid,ql,qr));
if(mid < qr) res = max(res,query(id << 1 | 1,mid + 1,r,ql,qr));
return res;
}
}sgt;
void range_add(double a,double b,int v){
if(a > b) swap(a,b);
int id_a = lower_bound(thetas.begin(),thetas.end(),a) - thetas.begin() + 1,
id_b = lower_bound(thetas.begin(),thetas.end(),b) - thetas.begin() + 1;
if(b - a > pi){
sgt._plus(1,1,len,1,id_a,v);
sgt._plus(1,1,len,id_b,len,v);
}else{
sgt._plus(1,1,len,id_a,id_b,v);
}
}
int query_max(double a,double b){
if(a > b) swap(a,b);
int id_a = lower_bound(thetas.begin(),thetas.end(),a) - thetas.begin() + 1,
id_b = lower_bound(thetas.begin(),thetas.end(),b) - thetas.begin() + 1;
if(b - a > pi)
return max(sgt.query(1,1,len,1,id_a),sgt.query(1,1,len,id_b,len));
return sgt.query(1,1,len,id_a,id_b);
}
int main(){
n = getint();
thetas.push_back(-pi);
thetas.push_back(pi);
for(int i = 1;i <= n;i++){
qs[i].opt = getint();
if(qs[i].opt == 1){
id[++num] = i;
qs[i].x0 = getint(), qs[i].y0 = getint(),
qs[i].x2 = getint(), qs[i].y2 = getint(), qs[i].v = getint();
thetas.push_back(atan2(qs[i].y0,qs[i].x0)),
thetas.push_back(atan2(qs[i].y2,qs[i].x2));
}else if(qs[i].opt == 2){
qs[i].v = getint();
}else if(qs[i].opt == 3){
qs[i].x0 = getint(), qs[i].y0 = getint();
thetas.push_back(atan2(qs[i].y0,qs[i].x0));
}else{
qs[i].v = getint();
}
}
sort(thetas.begin(),thetas.end());
thetas.erase(unique(thetas.begin(),thetas.end()),thetas.end());
len = thetas.size();
for(int i = 1;i <= n;i++){
if(qs[i].opt == 1){
range_add(atan2(qs[i].y0,qs[i].x0),atan2(qs[i].y2,qs[i].x2),qs[i].v);
}else if(qs[i].opt == 2){
int j = id[qs[i].v];
range_add(atan2(qs[j].y0,qs[j].x0),atan2(qs[j].y2,qs[j].x2),-qs[j].v);
id[qs[i].v] = -1;
}else if(qs[i].opt == 3){
printf("%d\n",
query_max(atan2(qs[i].y0,qs[i].x0),atan2(qs[i].y0,qs[i].x0)));
}else{
int j = id[qs[i].v];
if(j == -1) puts("oops!");
else{
printf("%d\n",
query_max(atan2(qs[j].y0,qs[j].x0),atan2(qs[j].y2,qs[j].x2)));
}
}
}
return 0;
}
```
RunID: [28847331](https://www.luogu.com.cn/record/28847331)，跑的还挺快。。。