2022 Hangzhou Electric Multi-School 1004 Ball

题目链接

Ball

题目大意

Topic given our two-dimensional plane$n$个点,Horizontal ordinate are no more than$100000$,Ask we choose three points,Three points constitute three sides of the perimeter of the median is the number of primes scheme is how much？

题解

Direct enumeration three points,势必会TLE;So we consider all edge build up,时间复杂度$O(n^2)$,And then according to the edge of the smallest size,Then, in turn, enumerated each edge,If the current edge is prime,Assuming that the current edge two endpoints for$a$ 和 $b$,We need to know the connection$a$The number of the edge is smaller than the current edge weights in the,连接$b$The number of edge is bigger than the current edge weights;Similarly, in turn, requires a.Direct enumeration not goozyet,我们考虑使用$bitset$进行优化,$p[i]$What are said to$i$Point distance less than or equal to the current edge,In the process of enumeration and maintenance can be.最终时间复杂度$O(n^{2}log(n^2))$.

代码

#include<iostream>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 2010, M = 200010;
#define x first
#define y second
typedef pair<int,int> PII;
PII a[maxn];
bool st[M];
int primes[M], cnt;
typedef struct node
{
    
    int a, b, c;
    bool operator < (const struct node &w) const {
    
        return c < w.c;
    }
}Node;
Node edges[maxn * maxn];
bitset<maxn> p[maxn];
int n, m;
void init(int n)
{
    
    for(int i = 2; i <= n; i ++){
    
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
    
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
int get_dist(PII a, PII b)
{
    
    return abs(a.x - b.x) + abs(a.y - b.y);
}
signed main()
{
    
    init(200000);
    st[1] = true;
    int t; cin >> t;
    while(t --){
    
        for(int i = 0; i < maxn; i ++) p[i].reset();
        cin >> n >> m;
        for(int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
        int k = 0;
        for(int i = 1; i <= n; i ++){
    
            for(int j = i + 1; j <= n; j ++){
    
                edges[k ++] = {
    i, j, get_dist(a[i], a[j])};
            }
        }
        int res = 0;
        sort(edges, edges + k);
        for(int i = 0; i < k; i ++){
    
            int a = edges[i].a, b = edges[i].b, c = edges[i].c;
            if(!st[c]) res += (p[a] ^ p[b]).count();
            p[a][b] = 1, p[b][a] = 1;
        }
        cout << res << endl;
    }
    return 0;
}