【ZOJ】4012 Your Bridge is under Attack

平面上随机n个点，然后给出m条直线，问直线上有几个点

\(n,m \leq 10^{5}\)

由于共线的点不会太多，于是我们可以建KD树出来直接查询，这条直线和某个矩形不相交则不搜索这个子树

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define ba 47

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

    if(c == '-') f = -1;

    c = getchar();

    }

    while(c >= '0' && c <= '9') {

    res = res * 10 +c - '0';

    c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

    out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,M,d;

pii p[MAXN];

#define lc(u) tr[u].lc

#define rc(u) tr[u].rc

#define siz(u) tr[u].siz

struct node {

    int lc,rc,siz,x,y;

    int x1,y1,x2,y2;

}tr[MAXN];

int rt,Ncnt;

void upmin(int &x,int y) {x = min(x,y);}

void upmax(int &x,int y) {x = max(x,y);}

void update(int u) {

    siz(u) = siz(lc(u)) + siz(rc(u)) + 1;

    tr[u].x1 = tr[u].x2 = tr[u].x;

    tr[u].y1 = tr[u].y2 = tr[u].y;

    upmin(tr[u].x1,min(tr[lc(u)].x1,tr[rc(u)].x1));

    upmax(tr[u].x2,max(tr[lc(u)].x2,tr[rc(u)].x2));

    upmin(tr[u].y1,min(tr[lc(u)].y1,tr[rc(u)].y1));

    upmax(tr[u].y2,max(tr[lc(u)].y2,tr[rc(u)].y2));

}

bool cmp(pii a,pii b) {

    if(d == 0) return a.fi < b.fi || (a.fi == b.fi && a.se < b.se);

    else return a.se < b.se || (a.se == b.se && a.fi < b.fi);

}

bool check(int u,int a,int b) {

    if(1LL * (tr[u].x2 - a) * b + 1LL * tr[u].y2 * a < 0) return false;

    if(1LL * (tr[u].x1 - a) * b + 1LL * tr[u].y1 * a > 0) return false;

    return true;

}

void build(int &u,int l,int r,int D) {

    if(l > r) return;

    u = ++Ncnt;

    if(l == r) {

	lc(u) = rc(u) = 0;

	tr[u].x = p[l].fi;tr[u].y = p[l].se;

	update(u);return;

    }

    d = D;

    int mid = (l + r) >> 1;

    nth_element(p + l,p + mid,p + r + 1,cmp);

    tr[u].x = p[mid].fi;tr[u].y = p[mid].se;

    build(lc(u),l,mid - 1,D ^ 1);

    build(rc(u),mid + 1,r,D ^ 1);

    update(u);

}

int Query(int u,int a,int b) {

    if(!check(u,a,b)) return 0;

    int res = 0;

    if(1LL * (tr[u].x - a) * b + 1LL * a * tr[u].y == 0) ++res;

    res += Query(lc(u),a,b);

    res += Query(rc(u),a,b);

    return res;

}

void Solve() {

    Ncnt = 0;rt = 0;

    tr[0].x1 = tr[0].y1 = 1e9 + 10;

    tr[0].y2 = tr[0].y2 = -1;

    read(N);read(M);

    for(int i = 1 ; i <= N ; ++i) {

	read(p[i].fi);read(p[i].se);

    }

    build(rt,1,N,0);

    int a,b;

    for(int i = 1 ; i <= M ; ++i) {

	read(a);read(b);

	out(Query(rt,a,b));enter;

    }

}

int main(){

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    int T;

    read(T);

    for(int i = 1 ; i <= T ; ++i) Solve();

    return 0;

}

巴特西

【ZOJ】4012 Your Bridge is under Attack

【ZOJ】4012 Your Bridge is under Attack

最新文章

热门文章