自动搬运

查看原文

来自洛谷，原作者为

	caeious 这个家伙很鸽，什么也没留下

搬运于2025-08-24 22:15:02，当前版本为作者最后更新于2019-12-29 11:24:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd: 在看了 SF 的文章后修了修格式；另外题解的渲染真的很丑。。。建议点击 “在 Ta 的博客查看”。

Solution

用极角做真的更简单诶。。。
在本题解中，极角的值域默认为 $(-\pi,\pi]$。

平面镜

设两个端点极角为 $\alpha,\ \beta(\alpha < \beta)$.
$\because$ 平面镜不经过原点
$\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$ 就好了。

浮点误差

$\because |x|,|y| <= 10^5$，输入中都是整点
$\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

#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，跑的还挺快。。。