QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372630#3034. AntennasSolitaryDream#AC ✓490ms6936kbC++172.1kb2024-03-31 16:53:482024-03-31 16:53:50

Judging History

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

  • [2024-03-31 16:53:50]
  • 评测
  • 测评结果:AC
  • 用时:490ms
  • 内存:6936kb
  • [2024-03-31 16:53:48]
  • 提交

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

详细

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