QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372611 | #3034. Antennas | SolitaryDream# | WA | 270ms | 3628kb | C++17 | 2.1kb | 2024-03-31 16:34:42 | 2024-03-31 16:34:43 |
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<=n; 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,n) 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: 0
Wrong Answer
time: 270ms
memory: 3628kb
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:
wrong answer 66160th lines differ - expected: '1 2 3', found: '-1 -1 0 '