QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#849528#8468. Collinear ArrangementsliyujiaTL 1ms7928kbC++171.6kb2025-01-09 16:07:272025-01-09 16:07:28

Judging History

你现在查看的是最新测评结果

  • [2025-01-09 16:07:28]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:7928kb
  • [2025-01-09 16:07:27]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
const int N = 500005;
int n, q, x[N], y[N], id[N], X1, Y1, X2, Y2;
gp_hash_table <int, int> mp;
int calc(int x, int y){
	int ans = 1;
	if(x < 0) x = -x, ans = -ans;
	if(y < 0) y = -y, ans = -ans;
	int g = __gcd(x, y); x /= g, y /= g;
	return (x * (int)3e9 + y) * ans;
}
int crs(int id){ return (X1 - x[id]) * (Y2 - y[id]) - (X2 - x[id]) * (Y1 - y[id]);}
int cal(int l, int r, int cof){
	int ans = 0, mid = l + r >> 1;
	if(r - l <= 2) for(int i = l; i <= r; i++) ans += !crs(i);
	else if(crs(mid) * cof < 0) ans = cal(mid + 1, r, cof);
	else ans = cal(l, mid, cof); return ans;
}
int slv(int l, int r, int cof){
	int L = l, R = r, id = l;
	while(L + 3 < R){
		int mid = L + R >> 1, p1 = crs(mid) * cof, p2 = crs(mid + 1) * cof;
		if(p1 < p2) l = mid + 1;
		else r = mid;
	} for(int i = L; i <= R; i++) if(crs(i) * cof > crs(id) * cof) id = i;
	return cal(l, id, cof) + cal(id + 1, r, -cof);
}
signed main(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	while(q--){
		int t, ans = 0;
		cin >> t >> X1 >> Y1;
		if(t == 1){
			mp.clear();
			for(int i = 1; i <= n; i++) ans += mp[calc(x[i] - X1, y[i] - Y1)]++;
			cout << ans << '\n';
		} else{
			cin >> X2 >> Y2; int cof = 1;
			if(crs(2) < crs(1)) cof = -1;
			int l = 1, r = n;
			while(l < r){
				int mid = l + r + 1 >> 1;
				if(crs(1) * cof > crs(mid) * cof) r = mid - 1;
				else l = mid;
			}
			cout << slv(1, l, cof) + slv(l + 1, n, -cof) << '\n';
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7928kb

input:

5 3
0 0
2 0
2 1
1 2
0 2
1 1 1
2 1 1 2 2
1 2 2

output:

1
1
2

result:

ok 3 number(s): "1 1 2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7660kb

input:

3 1
0 0
1 0
0 1
2 1 1 2 2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Time Limit Exceeded

input:

1000 1
-139438978 -172098481
-125097652 -169056403
155419484 -28898293
186215972 6874955
240691742 77644763
334255616 236444333
342049790 274206233
342049766 274611851
342049472 275025569
342049298 275242193
342048794 275724449
341967248 297262013
341966000 297569423
341963012 298092233
341960624 29...

output:


result: