cfgym100729I

201707 （ACM）计算几何

题意

• s(<=250000)个攻击，范围是r(<=20)，两个攻击的距离不会小于r。w(<=10)堵墙，攻击没经过一堵墙，攻击范围减少1。
• 求p(<=10000)个人会被哪些点攻击到，输出坐标。
• 坐标范围[-10000,10000]

题解

• 因为攻击的分布不会很稠密，所以每个人被攻击到的点很少。
• 考虑每个人最近的几个点如何枚举？
  
  • 枚举攻击的一个坐标，另一个坐标的最小值可以算出来。
  • 枚举另一个坐标直到人和攻击的距离大于r。

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
struct TPoint {
    ll x,y;
};
TPoint operator - (const TPoint &a,const TPoint &b) {
    TPoint res={a.x-b.x,a.y-b.y};
    return res;
}
bool operator < (const TPoint &a,const TPoint &b) {
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
double len(const TPoint &a) {
    return sqrt(a.x*a.x+a.y*a.y);
}
double dis(const TPoint &a,const TPoint &b) {
    return len(b-a);
}
ll cross(const TPoint &a,const TPoint &b,const TPoint &c) {
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool seg_inter(TPoint &a,TPoint &b,TPoint &c,TPoint &d) {
    return 
    max(a.x,b.x)>=min(c.x,d.x) && max(c.x,d.x)>=min(a.x,b.x) &&
    max(a.y,b.y)>=min(c.y,d.y) && max(c.y,d.y)>=min(a.y,b.y) &&
    cross(a,b,c)*cross(a,b,d)<=0 &&
    cross(c,d,a)*cross(c,d,b)<=0; 
}
set<int> s[20007];
TPoint wl[15],wr[15];
vector<TPoint> ans;
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        int n,r,w,m;scanf("%d%d%d%d",&n,&r,&w,&m);
        ///init
        rep(i,0,20007) s[i].clear();
        ///read
        rep(i,0,n) {
            int x,y;scanf("%d%d",&x,&y);
            s[x+10000].insert(y);
        }
        rep(i,0,w) {
            int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
            wl[i]={a,b};
            wr[i]={c,d};
        }
        ///solve
        while(m--) {
            ///init
            ans.clear();
            ///read
            int x,y;scanf("%d%d",&x,&y);
            ///solve
            TPoint p1={x,y};
            rep(i,-r,r+1) {
                int xx=x+i,yy=ceil(y-sqrt(r*r-i*i));
                int k=xx+10000;
                if(k<0||k>20000) continue;
                set<int>::iterator it = s[k].lower_bound(yy);
                while(it!=s[k].end()) {
                    TPoint p2={xx,*it++};
                    if(dis(p1,p2)>r) break;
                    int x=0;
                    rep(j,0,w) {
                        if(seg_inter(p1,p2,wl[j],wr[j])) ++x;
                    }
                    if(dis(p1,p2)<=r-x) ans.pb(p2);
                }
            }
            sort(ans.begin(),ans.end());
            printf("%d ",sz(ans));
            rep(i,0,sz(ans)) {
                printf("(%lld,%lld) ",ans[i].x,ans[i].y);
            }
            puts("");
        }
    }
    return 0;
}