QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372630 | #3034. Antennas | SolitaryDream# | AC ✓ | 490ms | 6936kb | C++17 | 2.1kb | 2024-03-31 16:53:48 | 2024-03-31 16:53:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
struct Point {
ll x,y;
Point operator +(const Point &s) const{
return {x+s.x,y+s.y};
}
Point operator -(const Point &s) const{
return {x-s.x,y-s.y};
}
};
ll det(Point a,Point b) {
return a.x*b.y-a.y*b.x;
}
bool operator <(const Point &a,const Point &b) {
return det(a,b)>0;
}
const int N=50005;
Point a[N],b[N];
int n,m;
ll sum[N];
void add(int x) {
for(; x<=m; x+=x&-x) {
sum[x]++;
}
}
ll qry(int x) {
ll s=0;
for(; x; x^=x&-x) {
s+=sum[x];
}
return s;
}
ll calc(Point u,Point v,Point p0,Point p1,Point p2,Point p3,int f) {
vector<pair<Point,int>> g;
FOR(i,0,m-1) {
if(det(p1-p0,b[i]-p0)>=0 && det(p3-p2,b[i]-p2)>=0) {
// if(f==0) cerr << i << endl;
g.push_back({b[i]-u,0});
}
}
sort(g.begin(),g.end());
FOR(i,0,g.size()-1) {
Point p=g[i].first+u-v;
swap(p.x,p.y);
g[i]={p,i+1};
}
sort(g.begin(),g.end());
ll s=0;
FOR(i,0,m) sum[i]=0;
for(auto [p,x]: g) {
// if(f==0) cerr << x << endl;
s+=qry(x);
add(x);
}
if(f) s=g.size()*((ll)g.size()-1)/2-s;
return s;
}
void solve() {
cin >> n;
FOR(i,0,n-1) cin >> a[i].x >> a[i].y;
a[n]=a[0];
cin >> m;
FOR(i,0,m-1) cin >> b[i].x >> b[i].y;
int q;
cin >> q;
while(q--) {
int u0,v0;
cin >> u0 >> v0;
int u1=(u0+1)%n,v1=(v0+1)%n;
ll res=calc(a[u1],a[u0],a[u0],a[v1],a[v0],a[u1],0);
// cerr << res << '\n';
res-=calc(a[u0],a[v0],a[u0],a[v0],a[v0],a[u1],1);
res-=calc(a[v1],a[u1],a[u0],a[v1],a[v1],a[u1],1);
cout << res << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 273ms
memory: 3604kb
input:
116799 4 0 2 2 3 2 1 0 0 2 1 1 1 2 6 1 3 1 2 0 2 0 3 0 1 2 3 4 0 2 2 3 2 1 0 0 2 1 1 1 2 6 1 2 2 3 0 2 0 1 1 3 0 3 4 0 2 1 3 3 1 0 0 2 1 2 2 1 6 0 2 0 3 1 2 0 1 1 3 2 3 5 0 2 1 3 2 3 3 1 0 0 2 1 2 2 1 10 2 3 0 1 1 2 1 4 1 3 0 4 2 4 0 3 0 2 3 4 5 0 2 1 3 2 3 3 1 0 0 2 1 2 2 1 10 2 4 2 3 3 4 1 2 ...
output:
0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 ...
result:
ok 116799 lines
Test #2:
score: 0
Accepted
time: 358ms
memory: 6936kb
input:
6 3 -1000000000 -1000000000 -1000000000 1000000000 1000000000 -1000000000 50000 -157866428 -481268129 -943828535 -404551206 -702156200 -918976587 -930672851 -662946583 -701356764 -690150251 -125890933 -15199649 -454987413 -601182432 -796857455 -452853385 -364662709 -332922528 -446377184 -59908020 -...
output:
422781691 405698933 421494376 90964408 112140449 58183510 0 86959753 401170255 0 83964813 77431438 36622679 0 0 0 201707235 298189155 0 20661817 1108613238 83335 103419782 17196828 0 109534039 102221733 35500923 0 107684911 381431817 0 100815183 107832883 20782102 28845692 14952512 28864912 378...
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 490ms
memory: 3608kb
input:
150000 10 128337801 981646274 680824665 718733451 973259647 181288879 893942524 -425401883 473169741 -869603585 -128337801 -981646274 -680824665 -718733451 -973259647 -181288879 -893942524 425401883 -473169741 869603585 2 0 900000000 0 -900000000 10 4 8 1 2 6 7 5 6 0 8 6 8 1 8 3 4 5 7 0 6 10 12833...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 150000 lines