<h1 id="heading">题目</h1>
{% fold 点击显/隐题目 %}
<div class="oj"><div class="part" title="Description">
The art galleries of the new and very futuristic building of the Center for Balkan Cooperation have the form of polygons (not necessarily convex). When a big exhibition is organized, watching over all of the pictures is a big security concern. Your task is that for a given gallery to write a program which finds the surface of the area of the floor, from which each point on the walls of the gallery is visible. On the figure 1. a map of a gallery is given in some co-ordinate system. The area wanted is shaded on the figure 2.
</div><div class="part" title="Input">
The number of tasks T that your program have to solve will be on the first row of the input file. Input data for each task start with an integer N, 5 &lt;= N &lt;= 1500. Each of the next N rows of the input will contain the co-ordinates of a vertex of the polygon ? two integers that fit in 16-bit integer type, separated by a single space. Following the row with the co-ordinates of the last vertex for the task comes the line with the number of vertices for the next test and so on.
</div><div class="part" title="Output">
For each test you must write on one line the required surface - a number with exactly two digits after the decimal point (the number should be rounded to the second digit after the decimal point).
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
1
7
0 0
4 4
4 7
9 7
13 -1
8 -6
4 -4
</div><div class="output part" title="Sample Output">
80.00
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
半平面交模板题,样例比较严格,能卡掉不严谨的板子 
网上搜到的好多AC代码都WA,可能是数据加强了
如果之前的点在新加入的边上时,不需要从队列删除 
在这里卡了好久
<h1 id="heading-2">代码</h1>
{% fold 点击显/隐代码 %}```cpp Art Gallery <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份 
#include <algorithm> 
#include <cmath> 
#include <cstdio> 
#include <cstring>
using namespace std;
#define Log(format, ...) // printf(format, ##VA_ARGS)
/* 计算几何模板 */
const double eps = 1e-8; 
const double INF = 0x4242424242424242; 
inline int sgn(const double &amp;x) { 
if (fabs(x) &lt; eps) 
return 0; 
return x &gt; 0 ? 1 : -1; 
}
struct Vector; 
struct Segment; 
double Cross(const Vector &amp;, const Vector &amp;); 
int Point_Segment(const Vector &amp;, const Segment &amp;);
struct Vector { 
double x, y; 
int n; 
Vector(double _x = 0, double _y = 0, int _n = 0) : x(_x), y(_y), n(_n) {} 
bool operator==(const Vector &amp;rhs) const { 
return sgn(x - rhs.x) == 0 &amp;&amp; sgn(y - rhs.y) == 0; 
} 
bool operator!=(const Vector &amp;rhs) const { return !(this == rhs); } 
bool operator&lt;(const Vector &amp;rhs) const { 
if (sgn(y - rhs.y) == 0) 
return sgn(x - rhs.x) &lt; 0; 
return sgn(y - rhs.y) &gt; 0; 
} 
Vector operator+(const Vector &amp;rhs) const { 
return Vector(x + rhs.x, y + rhs.y); 
} 
Vector operator-(const Vector &amp;rhs) const { 
return Vector(x - rhs.x, y - rhs.y); 
} 
Vector operator(const double &amp;rhs) const { 
return Vector(x * rhs, y * rhs); 
} 
Vector operator/(const double &amp;rhs) const { 
return Vector(x / rhs, y / rhs); 
} 
double getAngle() { return atan2(y, x); } 
double squre() const { return x * x + y * y; } 
double distance() const { return sqrt(squre()); } 
void print(bool flag = 0) const { 
Log(&quot;(%.2f %.2f)&quot;, x, y); 
if (flag) 
Log(&quot;\n&quot;); 
} 
}; 
typedef Vector Point; 
struct Segment { 
Point a, b; 
Segment() {} 
Segment(Point _a, Point _b) : a(_a), b(_b) {} 
bool operator&lt;(const Segment &amp;rhs) const { 
double angle1 = getAngle(); 
double angle2 = rhs.getAngle(); 
if (sgn(angle1 - angle2) == 0) 
return Point_Segment(a, rhs) &gt; 0; 
return sgn(angle1 - angle2) &lt; 0; 
} 
double getAngle() const { return toVector().getAngle(); } 
Vector toVector() const { return b - a; } 
double distance() const { return toVector().distance(); } 
void print(bool flag = 0) const { 
a.print(); 
Log(&quot; -&gt; &quot;); 
b.print(); 
if (flag) 
Log(&quot;\n&quot;); 
} 
};
/** 
* 读入一个点的坐标 
* @return 读入的点 
*/ 
inline Point read_Point() { 
double x, y; 
scanf(&quot;%lf%lf&quot;, &amp;x, &amp;y); 
return Point(x, y); 
}
inline double xmult(const Vector &amp;a, const Vector &amp;b, const Vector &amp;c) { 
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y); 
}
/** 
* 计算两个向量的叉积 
* @param a 向量1 
* @param b 向量2 
* @return 叉积 
*/ 
inline double Cross(const Vector &amp;a, const Vector &amp;b) { 
return a.x * b.y - a.y * b.x; 
}
/** 
* 计算两个向量的点积 
* @param a 向量1 
* @param b 向量2 
* @return 点积 
*/ 
inline double Dot(const Vector &amp;a, const Vector &amp;b) { 
return a.x * b.x + a.y * b.y; 
}
/** 
* 计算两点之间的距离 
* @param a 线段L1 
* @param b 线段L2 
* @return 两点间的距离 
*/ 
inline double Distance(const Point &amp;a, const Point &amp;b) { 
return (a - b).distance(); 
}
/** 
* 点和直线的关系 
* @param p 目标点 
* @param L 目标直线 
* @return 1 在左侧,0 在直线上,-1在右侧 
*/ 
inline int Point_Segment(const Vector &amp;p, const Segment &amp;L) { 
// printf(&quot;Point_segment %d\n&quot;, sgn(Cross(L.b - L.a, p - L.a))); 
return sgn(Cross(L.b - L.a, p - L.a)); 
}
/** 
* 计算两个线段(直线)是否平行 
* @param L1 L1的向量 
* @param L2 L2的向量 
* @return 返回是否平行 
*/ 
bool parallel(const Vector &amp;L1, const Vector &amp;L2) { 
return sgn(Cross(L1, L2)) == 0; 
}
/** 
* 计算两个直线的交点(需要确保不平行、重合) 
* @param L1 L1的向量 
* @param L2 L2的向量 
* @return 返回是否平行 
*/ 
Point getIntersection(const Segment &amp;L1, const Segment &amp;L2) { 
Point ret = L1.a; 
double t = ((L1.a.x - L2.a.x) * (L2.a.y - L2.b.y) - 
(L1.a.y - L2.a.y) * (L2.a.x - L2.b.x)) / 
((L1.a.x - L1.b.x) * (L2.a.y - L2.b.y) - 
(L1.a.y - L1.b.y) * (L2.a.x - L2.b.x)); 
ret.x += (L1.b.x - L1.a.x) * t; 
ret.y += (L1.b.y - L1.a.y) * t; 
return ret; 
}
/** 
* 计算两个线段的位置关系 
* @param L1 线段L1 
* @param L2 线段L2 
* @param p 返回交点坐标 
* @return 2 重叠 
1 相交 
0 延长线相交 
-1 平行 
-2 共线不交 
*/ 
inline int Segment_Segment(const Segment &amp;L1, const Segment &amp;L2, 
Point *p = NULL) { 
double a = L1.b.x - L1.a.x; 
double b = L2.b.x - L2.a.x; 
double c = L1.b.y - L1.a.y; 
double d = L2.b.y - L2.a.y; 
double f = a * d - b * c; 
// 平行或重叠 
if (sgn(f) == 0) { 
if (Point_Segment(L1.a, L2)) { 
// 平行 
return -1; 
} else { 
// 共线 
int len = max(max(Distance(L1.a, L2.a), Distance(L1.a, L2.b)), 
max(Distance(L1.b, L2.a), Distance(L1.b, L2.b))); 
if (sgn(len - L1.distance() - L2.distance()) &gt; 0) { 
// 共线不交 
return -2; 
} else { 
// 重叠 
return 2; 
} 
} 
} 
double g = L2.b.x - L1.a.x; 
double h = L2.b.y - L1.a.y; 
double t = (d * g - b * h) / f; 
double s = (-c * g + a * h) / f; 
if (p != NULL) 
*p = Point(L1.a.x + t * a, L1.a.y + t * c); 
// 在延长线上 
if (t &lt; 0 || t &gt; 1 || s &lt; 0 || s &gt; 1) 
return 0; 
// 线段相交 
return 1; 
}
/** 
* 判断点是否在多边形内部 
* @param p 需要判断的点 
* @param polygon 多边形点集,需要保证有序 
* @param numberOfSide 多边形边数 
* @return true 点在多边形内,false 点不在多边形内 
*/ 
bool Point_Polygon(const Point &amp;p, const Point polygon[], 
const int &amp;numberOfSide) { 
bool ok = 
Point_Segment(p, Segment(polygon[numberOfSide - 1], polygon[0])) &gt;= 0; 
for (int i = 1; i &lt; numberOfSide &amp;&amp; ok; ++i) { 
if (!(Point_Segment(p, Segment(polygon[i - 1], polygon[i])) &gt;= 0)) 
ok = false; 
} 
return ok; 
}
/** 
* 求多边形面积 
* @param p 点集 
* @param numOfSide 多边形边数 
* @return 返回多边形面积 
*/ 
double getArea(const Point p[], const int numberOfSide) { 
if (numberOfSide &lt; 3) 
return 0.0; 
double area = 0.0; 
for (int i = 2; i &lt; numberOfSide; ++i) 
area += fabs(0.5 * Cross(p[i] - p[0], p[i - 1] - p[0])); 
return area; 
}
/** 
* 求点集的凸包 
* @param p 点集,需要保证已经排序,并且点需要有不同的编号 
* @param numOfPoint 点集内的点的个数 
* @param vis 记录点对应的编号是否可以选择 
* @param ans 返回的凸包 
* @param begin 起始位置 
* @return 返回凸包上点的个数 
*/ 
int Convex_Hull(Point p[], int numOfPoint, bool vis[], Point ans[], 
int begin = 0) { 
int pos = begin - 1; 
// 右链 
for (int i = 0; i &lt; numOfPoint; ++i) { 
if (!vis[p[i].n]) { 
while (pos &gt; 0 &amp;&amp; 
Point_Segment(p[i], Segment(ans[pos], ans[pos - 1])) &gt; 0) { 
vis[ans[pos--].n] = false; 
} 
ans[++pos] = p[i]; 
vis[ans[pos].n] = true; 
} 
} 
// 左链 
for (int i = numOfPoint - 2; i &gt; 0; --i) { 
if (!vis[p[i].n]) { 
while (pos &gt; 0 &amp;&amp; 
Point_Segment(p[i], Segment(ans[pos], ans[pos - 1])) &gt; 0) { 
vis[ans[pos--].n] = false; 
} 
ans[++pos] = p[i]; 
vis[ans[pos].n] = true; 
} 
} 
return pos + 1; 
}
/** 
* 求直线集合的半平面交 
* @param s 线段集合 
* @param numOfSide 线段数目 
* @param ans 返回的多边形点 
* @param dequeue 需要的中间数组(记录用到的) 
* @return 返回结果多边形点的个数 
*/ 
int Half_Plane(Segment s[], int numOfSide, Point ans[], Segment dequeue[]) { 
sort(s, s + numOfSide);
<pre><code>int del = 1;
for (int i = 1; i &lt; numOfSide; ++i) {
 if (sgn(s[i].getAngle() - s[del - 1].getAngle()) != 0)
 s[del++] = s[i];
}
numOfSide = del;

for (int i = 0; i &lt; numOfSide; ++i) {
 s[i].print(1);
}

int bot = 0, top = 1;
dequeue[0] = s[0];
dequeue[1] = s[1];
for (int i = 2; i &lt; numOfSide; i++) {
 if (parallel(dequeue[top].toVector(), dequeue[top - 1].toVector()) ||
 parallel(dequeue[bot].toVector(), dequeue[bot + 1].toVector())) {
 dequeue[top].print(), dequeue[top - 1].print(1);
 dequeue[bot].print(), dequeue[bot + 1].print(1);
 return 0;
 }

 while (bot &lt; top &amp;&amp;
 Point_Segment(getIntersection(dequeue[top], dequeue[top - 1]),
 s[i]) &lt; 0)
 top--;
 while (bot &lt; top &amp;&amp;
 Point_Segment(getIntersection(dequeue[bot], dequeue[bot + 1]),
 s[i]) &lt; 0)
 bot++;
 dequeue[++top] = s[i];
}

while (bot &lt; top &amp;&amp;
 Point_Segment(getIntersection(dequeue[top], dequeue[top - 1]),
 dequeue[bot]) &lt; 0)
 top--;
while (bot &lt; top &amp;&amp;
 Point_Segment(getIntersection(dequeue[bot], dequeue[bot + 1]),
 dequeue[top]) &lt; 0)
 bot++;

//计算交点(注意不同直线形成的交点可能重合)
if (bot + 1 &gt;= top)
 return 0;

int len = 0;
for (int i = bot; i &lt; top; i++)
 ans[len++] = getIntersection(dequeue[i], dequeue[i + 1]);
if (bot &lt; top + 1)
 ans[len++] = getIntersection(dequeue[bot], dequeue[top]);

return len;
</code></pre>
}
const int maxn = 1505; 
bool vis[maxn]; 
Point p[maxn]; 
Point ans[maxn]; 
Segment s[maxn]; 
Segment deq[maxn];
int main() { 
int T; 
scanf(&quot;%d&quot;, &amp;T); 
while (T--) { 
int n; 
scanf(&quot;%d&quot;, &amp;n); 
for (int i = 0; i &lt; n; ++i) { 
p[i] = read_Point(); 
p[i].n = i; 
} 
for (int i = 0; i &lt;= n; ++i) 
s[i] = Segment(p[(i + 1) % n], p[i]);
<pre><code> int len = Half_Plane(s, n, ans, deq);

 for (int i = 0; i &lt; len; ++i)
 ans[i].print(1);

 if (len == 0) {
 printf(&quot;0.00\n&quot;);
 } else {
 double area = getArea(ans, len);
 if (sgn(area) &lt;= 0)
 area = 0.0;
 printf(&quot;%.2f\n&quot;, area);
 }
}
return 0;
</code></pre>
}
<pre style="background-color:#fff">{% endfold %}</pre>

POJ 1279.Art Gallery