题目描述
在圣若昂节期间，人们会放飞天灯。给定L LL个大天灯和S SS个小天灯的位置（二维平面上的点），需要统计有多少个小天灯位于任意三个大天灯构成的三角形内部或边界上。
输入包含多个测试用例。对于每个测试用例，第一行是L LL，随后L LL行是大天灯坐标，接着一行是S SS，随后S SS行是小天灯坐标。输出为满足条件的小天灯数量。
约束条件：
3 ≤ L ≤ 10000 3 \leq L \leq 100003≤L≤10000，1 ≤ S ≤ 50000 1 \leq S \leq 500001≤S≤50000，0 ≤ x , y ≤ 2 30 0 \leq x, y \leq 2^{30}0≤x,y≤230。所有点互不相同，且至少有三个大天灯不共线。
问题分析
直接枚举所有( L 3 ) \binom{L}{3}(3L)个三角形对每个小点进行测试是不可行的，因为L LL最大可达10 4 10^4104，三角形数量约为O ( 10 12 ) O(10^{12})O(1012)。
需要寻找更高效的方法。观察一个关键几何性质：
如果一个点位于某个由大点构成的三角形内部，那么该点必然位于这些大点的凸包内部（或边界上）。反之，如果点位于凸包内部，则一定存在凸包上的三个点构成的三角形包含该点。
这一性质的证明思路：对凸包进行三角剖分（例如固定一个顶点，与其他顶点连边形成扇形三角形），凸包内部的任何点必然落在某个剖分三角形内。
因此，原问题等价于：统计位于大点凸包内部或边界上的小点数量。
解题思路
1. 计算凸包
使用Andrew \texttt{Andrew}Andrew算法在O ( L log L ) O(L \log L)O(LlogL)时间内求凸包。算法步骤：
- 将所有点按x xx坐标（若相同则按y yy）升序排序。
- 从左到右扫描构建下凸包，保证每次转向为逆时针（叉积≥ 0 \geq 0≥0）。
- 从右到左扫描构建上凸包。
- 合并得到完整的凸包顶点序列（逆时针顺序，无重复起点）。
2. 判断点是否在凸多边形内
凸多边形（顶点逆时针顺序）内部判断可以做到O ( log n ) O(\log n)O(logn)：
- 首先检查点是否位于第一个顶点与相邻两条边的夹角内（通过叉积判断）。
- 然后二分查找该点位于哪两条射线之间（即找到最大的i ii使得P 0 P i → \overrightarrow{P_0 P_i}P0Pi在P 0 P → \overrightarrow{P_0 P}P0P的逆时针侧）。
- 最后判断点是否在三角形△ P 0 P i P i + 1 \triangle P_0 P_i P_{i+1}△P0PiPi+1内（叉积判断，包含边界）。
注意：边界上的点（在线段上）也算作内部，需要特殊处理。
3. 遍历小点并统计
对每个小点，调用O ( log L ) O(\log L)O(logL)的凸包包含判断，总复杂度O ( ( L + S ) log L ) O((L + S) \log L)O((L+S)logL)，可以满足题目要求。
4. 处理细节
- 凸包大小若小于3 33，则没有三角形，答案为0 00（但题目保证至少三个点不共线，因此凸包至少为三角形）。
- 所有运算使用
long long避免溢出（坐标最大2 30 2^{30}230，叉积可能达到2 60 2^{60}260）。 - 判断点在线段上时需要检查叉积为0 00且坐标在端点之间。
算法复杂度
- 凸包：O ( L log L ) O(L \log L)O(LlogL)
- 每个小点查询：O ( log L ) O(\log L)O(logL)
- 总复杂度：O ( ( L + S ) log L ) O((L + S) \log L)O((L+S)logL)，空间复杂度O ( L ) O(L)O(L)
代码实现
// Saint John Festival// UVa ID: 13024// Verdict: Accepted// Submission Date: 2026-06-02// UVa Run Time: 0.100s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;structPoint{ll x,y;Point(){}Point(ll x,ll y):x(x),y(y){}booloperator<(constPoint&p)const{returnx<p.x||(x==p.x&&y<p.y);}Pointoperator-(constPoint&p)const{returnPoint(x-p.x,y-p.y);}};llcross(constPoint&a,constPoint&b){returna.x*b.y-a.y*b.x;}lldot(constPoint&a,constPoint&b){returna.x*b.x+a.y*b.y;}llcross(constPoint&o,constPoint&a,constPoint&b){returncross(a-o,b-o);}// 判断点 p 是否在线段 ab 上（包括端点）boolonSegment(constPoint&p,constPoint&a,constPoint&b){if(cross(a,b,p)!=0)returnfalse;ll minx=min(a.x,b.x),maxx=max(a.x,b.x);ll miny=min(a.y,b.y),maxy=max(a.y,b.y);returnp.x>=minx&&p.x<=maxx&&p.y>=miny&&p.y<=maxy;}// 凸包（Andrew 算法）vector<Point>convexHull(vector<Point>pts){intn=pts.size();if(n<=1)returnpts;sort(pts.begin(),pts.end());vector<Point>hull(2*n);intk=0;// 下凸包for(inti=0;i<n;++i){while(k>=2&&cross(hull[k-2],hull[k-1],pts[i])<=0)--k;hull[k++]=pts[i];}// 上凸包intt=k+1;for(inti=n-2;i>=0;--i){while(k>=t&&cross(hull[k-2],hull[k-1],pts[i])<=0)--k;hull[k++]=pts[i];}hull.resize(k-1);returnhull;}// 判断点是否在凸多边形内部或边界上（凸多边形顶点逆时针）boolpointInConvexPolygon(constvector<Point>&poly,constPoint&p){intn=poly.size();if(n==0)returnfalse;// 检查是否在第一个顶点的扇形区域内if(cross(poly[0],poly[1],p)<0||cross(poly[0],poly[n-1],p)>0)returnfalse;// 二分查找所在三角形intlo=1,hi=n-1;while(hi-lo>1){intmid=(lo+hi)/2;if(cross(poly[0],poly[mid],p)>=0)lo=mid;elsehi=mid;}// 判断是否在三角形 poly[0], poly[lo], poly[hi] 内returncross(poly[lo],poly[hi],p)>=0||onSegment(p,poly[lo],poly[hi]);}intmain(){ios::sync_with_stdio(false);cin.tie(0);intL;while(cin>>L){vector<Point>large(L);for(inti=0;i<L;++i)cin>>large[i].x>>large[i].y;vector<Point>hull=convexHull(large);intS;cin>>S;intans=0;for(inti=0;i<S;++i){Point p;cin>>p.x>>p.y;if(pointInConvexPolygon(hull,p))++ans;}cout<<ans<<'\n';}return0;}总结
本题的核心在于将“三角形包含”问题转化为“凸包包含”问题，从而将复杂度从O ( L 3 S ) O(L^3 S)O(L3S)降低到O ( ( L + S ) log L ) O((L+S) \log L)O((L+S)logL)。利用凸包和二分查找，可以在大数据范围内高效求解。该技巧在计算几何中十分常见，值得熟练掌握。
