从从
提供一个
首先我们可以考虑观察一下样例和大样例,不难发现所有答案均在
首先一个折点的话一定无法将矩形分为两块,所以不合法。
两个折点的话即为通过一条直线将矩形分为两半,这条直线可以水平也可以竖直,所以对于这种情况,我们只需要对
三个折点的话随便画一下就会发现,最终的情况一定是隔离起来一个左上角或者右下角,如图:
考虑如何维护,显然可以把这个东西按照类似二位偏序或者说二维数点来写,先按照
如果以上的判断都不合法的话那么显然最终答案即为
显然这个时候我们是可以隔离出来任意数量的整点了,比较好理解,考虑一下如果想更多地包含新的点,将中间那块凸起略移动一下
至此我们便以
x1
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template< typename T = int >
25inline T read(void);
26
27int N;
28struct Coord{int x, y;}a[MAXN];
29int bucx[MAXN], bucy[MAXN];
30
31class SegTree{
32private:
33 int tr[MAXN << 2];
34
35
36
37public:
38 void Clear(int p = 1, int gl = 1, int gr = N + 1){
39 if(gl == gr)return tr[p] = 0, void();
40 Clear(LS, gl, MID);
41 Clear(RS, MID + 1, gr);
42 tr[p] = 0;
43 }
44 void Pushup(int p){tr[p] = tr[LS] + tr[RS];}
45 void Modify(int idx, int v = 1, int p = 1, int gl = 1, int gr = N + 1){
46 if(gl == gr)return tr[p] += v, void();
47 if(idx <= MID)Modify(idx, v, LS, gl, MID);
48 else Modify(idx, v, RS, MID + 1, gr);
49 Pushup(p);
50 }
51 bool QueryR(int val, int cur = 0, int p = 1, int gl = 1, int gr = N + 1){
52 // printf("Querying %d ~ %d, cur = %d\n", gl, gr, cur);
53 if(cur + tr[p] == val)return true;
54 if(gl == gr)return false;
55 if(cur + tr[LS] >= val)return QueryR(val, cur, LS, gl, MID);
56 else return QueryR(val, cur + tr[LS], RS, MID + 1, gr);
57 }
58 bool QueryL(int val, int cur = 0, int p = 1, int gl = 1, int gr = N + 1){
59 // printf("Querying %d ~ %d, cur = %d\n", gl, gr, cur);
60 if(cur + tr[p] == val)return true;
61 if(gl == gr)return false;
62 if(cur + tr[RS] >= val)return QueryL(val, cur, RS, MID + 1, gr);
63 else return QueryL(val, cur + tr[RS], LS, gl, MID);
64 }
65}st;
66
67int main(){
68 // freopen("ex_line2.in", "r", stdin);
69 // freopen("out.txt", "w", stdout);
70 int T = read();
71 while(T--){
72 bool flag(false);
73 memset(bucx, 0, sizeof(int) * (N + 10)), memset(bucy, 0, sizeof(int) * (N + 10));
74 N = read();
75 for(int i = 1; i <= N; ++i)
76 a[i].x = read() + 1, a[i].y = read() + 1, bucx[a[i].x]++, bucy[a[i].y]++;
77 a[N + 1].x = a[N + 1].y = 0;
78 for(int i = 1; i <= N; ++i){
79 bucx[i] += bucx[i - 1], bucy[i] += bucy[i - 1];
80 if(bucx[i] == N >> 1 || bucy[i] == N >> 1){printf("2\n"), flag = true; break;}
81 }if(flag)continue;
82 sort(a + 1, a + N + 1, [](const Coord &a, const Coord &b)->bool{return a.x == b.x ? a.y < b.y : a.x < b.x;});
83 st.Clear();
84 for(int i = N; i >= 1; --i){
85 st.Modify(a[i].y);
86 while(a[i - 1].x == a[i].x)st.Modify(a[--i].y);
87 if(st.QueryR(N / 2)){printf("3\n"), flag = true; break;}
88 }if(flag)continue;
89 st.Clear();
90 for(int i = 1; i <= N; ++i){
91 st.Modify(a[i].y);
92 while(a[i + 1].x == a[i].x)st.Modify(a[++i].y);
93 if(st.QueryL(N / 2)){printf("3\n"), flag = true; break;}
94 }if(flag)continue;
95 printf("4\n");
96 }
97 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
98 return 0;
99}
100
101template < typename T >
102inline T read(void){
103 T ret(0);
104 int flag(1);
105 char c = getchar();
106 while(c != '-' && !isdigit(c))c = getchar();
107 if(c == '-')flag = -1, c = getchar();
108 while(isdigit(c)){
109 ret *= 10;
110 ret += int(c - '0');
111 c = getchar();
112 }
113 ret *= flag;
114 return ret;
115}
update-2022_11_22 初稿
update-2022_11_22 修改了一处细节错误