加载中…HDU 3867 Light And Shadow Multi-University Training Contest 3 - Host by BIT
(2011-07-21 20:00:29)
标签：
hdu3876lightandshadowit |
分类： 计算几何 |
题目描述：
中心有一个光源，附近有n个挡板，问你有多少个挡板可以被照到。
解题报告：
对每个点极角排序。扫描线，用映射二分堆维护线段集合，线段的排序函数是：当前扫描线距离各个线段的距离。
遇到线段的入点（哪个算入哪个算出看极角排序的顺序，自己定义），插入线段，查看堆顶是谁，标记为可以照到。遇到出点，删除之（故用映射二分堆，也可以用set），再次看堆顶，即可。
注意，一开始的扫描线要把当时越过扫描线的线段首先插入进去。
代码如下：
double
x, y, jd;
int
id;bool in;
bool
operator < (const pint &tmp)
const{return jd < tmp.jd;}
pint(double x, double y) : x(x), y(y){}
pint(){}
double
d3 = xmult(p3, p2, p1);
double
d4 = xmult(p4, p2, p1);
if (d3
* d4 <= 0 || fabs(d3) <eps ||
fabs(d4) < eps) return true;
return
false;
pint a,
b;
line(pint a, pint b) : a(a), b(b){}
line(){}
bool
operator < (const line
&tmp) const
{
pint xx = intersection(pint(0,
0), sta, a, b);
pint yy = intersection(pint(0,
0), sta, tmp.a, tmp.b);
return (xx.x * xx.x + xx.y *
xx.y + eps < yy.x * yy.x + yy.y * yy.y);
}
return
p3.x * p2.y - p2.x * p3.y < -eps;
while(scanf("%d", &n) !=
EOF)
{
h.init();
memset(vst, 0,
sizeof(vst));
memset(ans, 0,
sizeof(ans));
scanf("%lf%lf",
&sta.x, &sta.y);
for(int i = 0; i
< n + n; i += 2)
{
scanf("%lf%lf", &v[i].x,
&v[i].y);
scanf("%lf%lf", &v[i + 1].x,
&v[i + 1].y);
v[i].x -= sta.x; v[i].y -= sta.y;
v[i + 1].x -= sta.x; v[i + 1].y -= sta.y;
v[i].id = v[i + 1].id = i / 2;
if (CrossLeft(v[i], v[i + 1]))
v[i].in =
true, v[i + 1].in = false;
else v[i].in = false, v[i + 1].in = true;
v[i].jd = atan2(v[i].y, v[i].x);
v[i + 1].jd = atan2(v[i + 1].y, v[i +
1].x);
jeo[i / 2] = line(v[i], v[i + 1]);
}
sort(v, v + n + n);
sta = pint(100, 0);
for(int i = 0; i
< n + n; i++)
{
if (v[i].in == false
&& !vst[v[i].id])
h.ins(v[i].id, jeo[v[i].id]);
else if (v[i].in == true)
vst[v[i].id] = true;
}
if (h.n != 0) ans[h.ind[1]] =
true;
for(int i = 0; i
< n + n; i++)
{
if (v[i].in)
{
sta =
v[i];
h.ins(v[i].id, jeo[v[i].id]);
if (h.n !=
0) ans[h.ind[1]] = true;
}else if (!v[i].in)
{
sta =
v[i];
line
tmp;
h.del(v[i].id, tmp);
if (h.n !=
0) ans[h.ind[1]] = true;
}
}
int ccnt = 0;
for(int i = 0; i
< n; i++) if (ans[i]) ccnt++;
printf("%d\n", ccnt);
}
中心有一个光源，附近有n个挡板，问你有多少个挡板可以被照到。
解题报告：
对每个点极角排序。扫描线，用映射二分堆维护线段集合，线段的排序函数是：当前扫描线距离各个线段的距离。
遇到线段的入点（哪个算入哪个算出看极角排序的顺序，自己定义），插入线段，查看堆顶是谁，标记为可以照到。遇到出点，删除之（故用映射二分堆，也可以用set），再次看堆顶，即可。
注意，一开始的扫描线要把当时越过扫描线的线段首先插入进去。
代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAXN 300000
#define _cp(a,b) ((a)<(b))
#define eps 1e-12
struct pint
{
}sta, v[MAXN];
double xmult(pint p1,pint p2,pint p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool insect(pint p1, pint p2, pint p3, pint p4) //
判断直线与线段是否相交，p1, p2是直线
{
}
pint intersection(pint u1,pint u2,pint v1,pint v2){
pint ret=u1;
double
t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
struct line
{
}jeo[MAXN];
bool CrossLeft(pint p2, pint p3)//是否严格左转，共线不算左转
{
}
int n;
typedef line elem_t;
struct heap{
elem_t h[MAXN];
int ind[MAXN],map[MAXN],n,p,c;
void init(){n=0;}
void ins(int i,elem_t e){
for
(p=++n;p>1&&_cp(e,h[p>>1]);h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);
h[map[ind[p]=i]=p]=e;
}
int del(int i,elem_t& e){
i=map[i];if (i<1||i>n) return
0;
for
(e=h[p=i];p>1;h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);
for
(c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;
}
int delmin(int& i,elem_t&
e){
if (n<1) return 0;i=ind[1];
for
(e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;
}
}h;
bool vst[MAXN], in[MAXN], ans[MAXN];
int main()
{
return 0;
}
喜欢
0
赠金笔