QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372611#3034. AntennasSolitaryDream#WA 270ms3628kbC++172.1kb2024-03-31 16:34:422024-03-31 16:34:43

Judging History

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

  • [2024-03-31 16:34:43]
  • 评测
  • 测评结果:WA
  • 用时:270ms
  • 内存:3628kb
  • [2024-03-31 16:34:42]
  • 提交

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;
}

详细

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 '