【WC2001】 摄影师的烦恼 解题报告

摄影师的烦恼

visible.pas(exe)

visible.in

visible.out

【问题描述】

摄影师Tension在他的3D工作室里布置了一些布景（假设所有的布景都是正四棱柱，并且都直接放在地板上）。

为了描述这些布景的位置，我们在地板上建立了直角坐标系，原点O处是Tension和他的照相机。对于每一个正四棱柱的布景，用它的底面正方形的中心坐标(x_c，y_c)来标识它的位置，用底面边长d和棱柱的高h来标识它的形状（如图）。同时，每一布景的放置都是规则的，也就是说，所有棱柱底面的棱都平行于坐标轴。当然，任意两个布景（正四棱柱）是不可能有重叠的部分。

对于站在坐标原点O的Tension而言(Tension趴在地上，高度视为0)，一个四棱柱表面上的某个点，当且仅当它与原点的连线（也就是观察者的视线）不再穿过任何四棱柱的表面（包括棱和顶点）时，才被认为是可见的；如果一个四棱柱表面上存在可见的点，那么我们就认为这个四棱柱是可见的，这时，Tension就可以从照相机里看到这个布景（全部或者一部分）。

当Tensoin布置完这些布景之后，他想要了解从他所站的位置到底能够看到多少布景，但是当布景相当多的时候，这着实让Tension苦恼。而您的任务，就是利用程序求出在坐标原点O可见的四棱柱的个数m。

【输入输出】

输入文件visible.in的第一行是一个正整数N，表示正四棱柱的总数。

从第2行至第N+1行，每行各有4个正整数x_i，y_i，d_i，h_i，用空格分隔开，表示一个正四棱柱的中心坐标、底边长和高。

输出文件visible.out只有一个整数m，表示可见的正四棱柱的个数。

【数据说明】

所有四棱柱的底面顶点坐标（x，y）都满足：

0＜x≤65000，0＜y≤65000；（也就是说，所有坐标都在第一象限内）

对于四棱柱的形状的限制有  0＜d≤65000，0＜h≤65000；

布景的总数为N，且1≤N≤1000。

【评分说明】

只有完全正确的输出才能够获得测试点的分数。

【解析】

       三维的计算几何问题不易解决，我们试图将它简化为二维的问题。

       注意到，由于长方体都在第一象限，一个长方体可见的充要条件是它的左上棱或前上棱可见：

       这样，我们可以将一个长方体简化为两条线段，每条线段除了位置信息外，还有高度信息。但是判断一个线段是否可见意味着需要判断线段上的每一个点都可见，题目中说坐标的位置是整数不代表线段是离散的，线段上的点的坐标仍然是实数。

既然不能判断一个线段可见，我们反其道而行之，转而判断它是否不可见。我们首先假设所有线段都可见，每处理一个线段，我们都将被这个线段所所对应的长方体挡住的线段的被挡住的部分设置为“不可见”。显然，我们需要按从左下角到右下角（从俯视图看）的顺序处理线段：

      

       现在问题来了：如何判断一个未处理的线段是否会被已处理的线段遮住？

       根据常识，我们应该用斜率的大小判断一个线段是否会被挡住，但遗憾的是，一个线段的各个点的斜率不同，左下角的点的斜率最大，左上角或右下角的斜率最小。但是，如果线段AB位于线段CD的左侧（x_B<x_D）则AB不可能可以遮住CD的右侧斜率小的部分，而遮不住CD左侧斜率大的部分。这样，当我们判断一段线段是否会被遮挡住时，只需要判断交点的斜率的大小关系，也就是图中的OP₁和OP₂的斜率：

对于每一次遮挡操作，我们将操作记录在对应的被遮挡的线段中，而不进行实际的操作。处理一个线段时，用零维扫描线判断该线段是否已被全部遮挡。

【实现细节】

我们首先设计一个线段类，操作用vector储存：

/*

a   |

    |

    |

    |

    |

    |

b   |----------------------

                         c

*/

struct segment_t

{

    long double ay, bx, by, cx;

    long double height;

    //延X轴方向的遮挡，即bc上的遮挡

    vector <pair<long double, long double> >operX;

    //延Y轴方向的遮挡，即ab上的遮挡 

    vector <pair<long double, long double> >operY;

};

接着我们处理输入：

int n;

read(n);

for (int i = 0; i<n; i++)

{

    int x, y, d, h;

    read(x); read(y); read(d); read(h);

    segment[i].bx = x - d / 2.0;

    segment[i].by = y - d / 2.0;

    segment[i].ay = y + d / 2.0;

    segment[i].cx = x + d / 2.0;

    segment[i].height = h;

}

之后将线段排序，点b位于左下角的线段排在前面，这是因为只有一个线段左下角的线段才可能完成遮住它：

bool operator<(segment_t a, segment_t b)

{

    if (int(a.bx) != int(b.bx))return a.bx<b.bx;

    else return a.by<b.by;

}

按顺序处理线段：

for (int i = 0; i<n; i++)

{

    if (uncovered(segment[i]))ans++;

    setcover(segment[i]);

}

cout << ans << endl;

写完了？当然没有，还差两个关键的函数——uncovered和setcover：

//判断一个线段是否被覆盖

bool uncovered(segment_t s)

{

    return false;

}

//覆盖可以被一个线段遮住的线段

void setcover(segment_t s)

{

}

这两个函数的实现留给读者，实现方式将在日后公布。