QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #121594 | #4778. Tracking RFIDs | momoyuu | WA | 296ms | 16196kb | C++17 | 3.1kb | 2023-07-08 15:09:42 | 2023-07-08 15:09:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll ccw(pair<ll,ll> a,pair<ll,ll> b,pair<ll,ll> c){
ll na = b.first - a.first;
ll nb = b.second - a.second;
ll ma = c.first - a.first;
ll mb = c.second - a.second;
if(na*mb-nb*ma>0) return 1;
if(na*mb-nb*ma<0) return -1;
if(na*ma+nb*mb<0) return 2;
if(na*na+nb*nb<ma*ma+mb*mb) return -2;
return 0;
}
bool ch(ll x1,ll y1,ll x2,ll y2,ll x3,ll y3,ll x4,ll y4){
ll tc = (x1-x2)*(y3-y1) + (y1-y2)*(x1-x3);
ll td = (x1-x2)*(y4-y1) + (y1-y2)*(x1-x4);
return tc*td<0;
}
void solve(){
ll s,r,w,p;
cin>>s>>r>>w>>p;
ll mask = 10040 + 100;
vector<set<ll>> d(30000);
for(int i = 0;i<s;i++){
ll x,y;
cin>>x>>y;
d[x+mask].insert(y);
}
vector<ll> bx(w),by(w),ex(w),ey(w);
for(int i = 0;i<w;i++) cin>>bx[i]>>by[i]>>ex[i]>>ey[i];
for(int i = 0;i<p;i++){
set<pair<ll,ll>> ans;
ll px,py;
cin>>px>>py;
for(ll xx = px - r;xx <= px + r;xx++){
ll nx = xx + mask;
auto itr = d[nx].lower_bound(py-r);
while(itr!=d[nx].end()){
pair<ll,ll> now = make_pair(xx,*itr);
ll dx = px - now.first;
ll dy = py - now.second;
if(dx*dx+dy*dy>r*r) break;
if(px==xx&&py==*itr){
ans.insert(now);
itr++;
continue;
}
int cnt = 0;
for(int j = 0;j<w;j++){
//if(ch(px,py,now.first,now.second,bx[j],by[j],ex[j],ey[j])) cnt++;
//if(ch(make_pair(px,py),make_pair(bx[j],by[j]),now)) continue;
//if(ch(make_pair(px,py),make_pair(ex[j],ey[j]),now)) continue;
//if(ch(make_pair(px,py),make_pair(bx[j],by[j]),make_pair(ex[j],ey[j]))&&ch(now,make_pair(bx[j],by[j]),make_pair(ex[j],ey[j]))) continue;
if(ccw(make_pair(px,py),now,make_pair(bx[j],by[j]))*ccw(make_pair(px,py),now,make_pair(ex[j],ey[j]))<0&&ccw(make_pair(bx[j],by[j]),make_pair(ex[j],ey[j]),make_pair(px,py))*ccw(make_pair(bx[j],by[j]),make_pair(ex[j],ey[j]),now)<0) cnt++;
if(ccw(make_pair(px,py),now,make_pair(bx[j],by[j]))*ccw(make_pair(px,py),now,make_pair(ex[j],ey[j]))==0&&ccw(make_pair(bx[j],by[j]),make_pair(ex[j],ey[j]),make_pair(px,py))*ccw(make_pair(bx[j],by[j]),make_pair(ex[j],ey[j]),now)==0){
cnt++;
}else if(ccw(make_pair(px,py),now,make_pair(bx[j],by[j]))*ccw(make_pair(px,py),now,make_pair(ex[j],ey[j]))==0){
cnt++;
}
}
//cout<<cnt<<" "<<xx<<" "<<*itr<<endl;
if(r-cnt>=0&&dx*dx+dy*dy<=(r-cnt)*(r-cnt)) ans.insert(now);
itr++;
}
}
cout<<ans.size();
for(auto&itr:ans) cout<<" ("<<itr.first<<","<<itr.second<<")";
cout<<endl;
}
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4556kb
input:
1 4 3 4 7 0 0 -1 3 2 3 11 5 -4 -1 5 -1 3 5 6 1 11 4 11 3 12 5 12 8 1 1 0 -2 4 4 11 2 13 5 13 7 14 5
output:
3 (-1,3) (0,0) (2,3) 1 (0,0) 0 0 1 (11,5) 0 0
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 296ms
memory: 16196kb
input:
62 4 3 4 7 0 0 -1 3 2 3 11 5 -4 -1 5 -1 3 5 6 1 11 4 11 3 12 5 12 8 1 1 0 -2 4 4 11 2 13 5 13 7 14 5 3 5 0 5 0 0 5 0 8 4 0 5 2 3 2 4 3 4 5 0 3 1 0 15 -10 -42 -9 -42 -8 -42 -11 -41 -11 -42 -11 -43 -10 -41 -10 -42 -10 -43 -9 -41 -9 -42 -9 -43 -8 -41 -8 -42 -8 -43 -7 -41 -7 -42 -7 -43 5 3 0 7 0 0 -1 -3...
output:
3 (-1,3) (0,0) (2,3) 1 (0,0) 0 0 1 (11,5) 0 0 1 (0,0) 2 (0,0) (5,0) 2 (0,0) (5,0) 3 (0,0) (5,0) (8,4) 3 (0,0) (5,0) (8,4) 0 1 (-10,-42) 0 1 (-10,-42) 2 (-10,-42) (-9,-42) 1 (-10,-42) 1 (-9,-42) 3 (-10,-42) (-9,-42) (-8,-42) 1 (-9,-42) 1 (-8,-42) 2 (-9,-42) (-8,-42) 1 (-8,-42) 0 1 (-8,-42) 0 3 (-1,-3...
result:
wrong answer 80th lines differ - expected: '2 (0,5) (5,5)', found: '0'