【poor几何】UVALive 5908 更新一下线段相交模板

Posted by Cww97 on 2016-02-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50641899
题目点这

题意:给S个传感器,每个传感器范围为R,有W堵墙,碰到墙传感器范围会少1,给P个物品,问每个物品可以被几个传感器感受到。

思路:观察数据发现R很小,可以以每个点位中心扫描穷举,(暴力的不要不要的)。
在这里主要存一下新的线段相交模板,之前写过一篇跨立的题解,那个代码是直接从从原来用pascal的时候的代码翻译过来,丑的令人发指(自己调试都要吐血了)= =
这次重新写了struct,借chao鉴xi了 miss_minor 的跨立写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;

struct point{
int x,y;
point(int x=0,int y=0):x(x),y(y){}
bool operator < (const point &a) const{
return a.x==x ? y<a.y : x<a.x;
}
point operator + (const point &a)const{
point ans;
ans.x=x+a.x;
ans.y=y+a.y;
return ans;
}
point operator - (const point &a)const{
point ans;
ans.x=x-a.x;
ans.y=y-a.y;
return ans;
}
int operator ^ (const point &a)const{
return x*a.y-y*a.x;
}
}po,tmp;

struct line{
point a,b;
void init(int ax=0,int ay=0,int bx=0,int by=0)
{a.x=ax;a.y=ay;b.x=bx;b.y=by;}
}l[20];

int S,R,W,P,X1,X2,Y1,Y2;
vector<point>p;
set<point>vis;

LL dis(point a,point b){
LL x=a.x-b.x,y=a.y-b.y;
return x*x+y*y;
}

bool xj(point p1,point p2,point p3,point p4){//xiangjiao
if (max(p1.x,p2.x)<min(p3.x,p4.x))return 0;
if (max(p1.y,p2.y)<min(p3.y,p4.y))return 0;
if (max(p3.x,p4.x)<min(p1.x,p2.x))return 0;
if (max(p3.y,p4.y)<min(p1.y,p2.y))return 0;//ju xin shi yan

LL x=(p3-p1)^(p2-p1);
LL y=(p4-p1)^(p2-p1);
LL z=(p1-p3)^(p4-p3);
LL w=(p2-p3)^(p4-p3);//KuaLi
return x*y<=0&&z*w<=0;
}

bool check(point a,point b){
if (vis.find(b)==vis.end())return 0;
LL d=dis(a,b); if (d>R*R) return 0;
int cnt=0;
for (int i=0;i<W;i++)
if (xj(a,b,l[i].a,l[i].b)) cnt++;
if (cnt>R)return 0;
return d<=(R-cnt)*(R-cnt);
}

int main(){
//freopen("fuck.in","r",stdin);
int T; scanf("%d",&T);
for (;T--;){
scanf("%d%d%d%d",&S,&R,&W,&P);
vis.clear();
for (int i=0;i<S;i++){
scanf("%d%d",&po.x,&po.y);
vis.insert(po);
}
for (int i=0;i<W;i++){
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
l[i].init(X1,Y1,X2,Y2);
}
for (int time=0;time<P;time++){
scanf("%d%d",&po.x,&po.y);
p.clear();
for (int i=po.x-R;i<=po.x+R;i++)
for(int j=po.y-R;j<=po.y+R;j++){
tmp.x=i; tmp.y=j;
if (check(po,tmp))p.push_back(tmp);
}
printf("%d",p.size());
for (int i=0;i<p.size();i++)
printf(" (%d,%d)",p[i].x,p[i].y);
puts("");
}
}
return 0;
}