闲扯
集训时侯讲到这题,然而出题人简洁的题解跟没有差不多,然后上网看applese大佬的博客终于看懂了,不违反基本法还是贴[转载]吧
题目链接
https://www.luogu.org/problemnew/show/CF1028F
转载来源
https://blog.csdn.net/effervescence/article/details/82142380
题意
给一个无限大的二维平面，$n(n≤2 \times 10^5)$次操作，
(1)在平面上加一个点（保证加入前不存在）
(2)在平面上删除一个点（保证删除时存在）
(3)给出一个点，以原点和这个点连成的直线为对称轴，问你至少要加几个点可以使得这个平面对称。
分析
首先我们猜一个结论，就是一个以原点为圆心的圆上的整点是不会很多的（具体我不会证）。
然后又因为如果这个平面对称，那么两个对称点到原点的距离肯定是相等的。那么我们每次加入或删除一个点时，记这个点到原点的距离为d，那我们暴力枚举这个以d为半径，原点为圆心的圆上其他的点，算出他们的对称轴，把这个对称轴的数值加上或减去2，然后把这个点和原点连成的直线所形成的对称轴的数值加上或减去1，之后每次O(1)回答答案就行了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
struct Point {
int x,y;
Point(int _x=0,int _y=0) {
x=_x,y=_y;
}
inline bool operator < (const Point &rhs) const {
return x==rhs.x?y<rhs.y:x<rhs.x;
}
inline Point F() {
Point p=Point(x,y);
if(x||y) {
int g=__gcd(p.x,p.y);
p.x/=g,p.y/=g;
}
return p;
}
inline Point operator + (const Point &rhs) const {
return Point(x+rhs.x,y+rhs.y).F();
}
};
int n,cnt;
map<ll,set<Point> >circle;
map<Point,int>exist;
Point o(0,0);
int main() {
read(n);
while(n--) {
int ty,x,y;
read(ty),read(x),read(y);
Point t=Point(x,y);
ll d=1ll*x*x+1ll*y*y;
if(ty==1) {
for(auto p:circle[d])
exist[p+t]+=2;
circle[d].insert(t);
exist[o+t]++,cnt++;
}
if(ty==2) {
circle[d].erase(circle[d].find(t));
for(auto p:circle[d])
exist[p+t]-=2;
exist[o+t]--,cnt--;
}
if(ty==3)
printf("%d\n",cnt-exist[o+t]);
}
}
|
一些补充
如果您已经看懂applese大佬的博客那么您可以不用看下面了,这些是我对我在阅读时一些疑惑的强行解释
由于对称轴已经有一点是固定的,那么它经过的另一点(除原点)不同肯定直线也就不同,那么对于两点$A(x_a,y_a),B(x_b,y_b)$,很显然它们的对称轴经过中点$C((x_a+x_b)/2,(y_a+y_b)/2)$,于是它们的对称轴其实就可以用$C$点表示,但是为了方便起见不妨用$C`(x_a+x_b,y_a+y_b)$表示对称轴,但注意要保证$(x_a+x_b)$与$(y_a+y_b)$是互质的,否则就可能有些在一条对称轴上的点算不到
所以$exist[PT]$其实就是表示关于过$(0,0)$与$PT$两点为对称轴的点的个数,询问就是总的点数减去对称的点数就好了
不含C++11特性代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define ri register int
using namespace std;
using namespace __gnu_pbds;
int n,tot;
template <class T>inline void read(T &x){x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
struct Pt{
int x,y;
Pt(int _x,int _y){x=_x,y=_y;}
Pt operator +(const Pt &b)const{
int p=gcd(x+b.x,y+b.y);
return Pt((x+b.x)/p,(y+b.y)/p);
}
bool operator <(const Pt &b)const{
return x==b.x?y<b.y:x<b.x;
}
};
map<ll,set<Pt> > c;
map<Pt,int> g;
int main(){
int op,x,y;
Pt O=Pt(0,0);tot=0;
read(n);
set<Pt>::iterator k;
while(n--){
read(op),read(x),read(y);
Pt pt=Pt(x,y);
ll dis=1ll*x*x+1ll*y*y;
if(op==1){
for(k=c[dis].begin();k!=c[dis].end();k++){g[*k+pt]+=2;}
c[dis].insert(pt);
tot++;g[O+pt]++;
}
else if(op==2){
c[dis].erase(c[dis].find(pt));
for(k=c[dis].begin();k!=c[dis].end();k++)g[*k+pt]-=2;
tot--;g[O+pt]--;
}
else{
printf("%d\n",tot-g[O+pt]);
}
}
return 0;
}
|