QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#849528 | #8468. Collinear Arrangements | liyujia | TL | 1ms | 7928kb | C++17 | 1.6kb | 2025-01-09 16:07:27 | 2025-01-09 16:07:28 |
Judging History
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...