简单的凸包加上扫描顶点。
题意是给出一个多边形，对这个多边形构造一个凸包，问有多少条边是在凸包上的，凸包上有多少个区域是缺了的。求出来以后乘以给出的权值，就是答案。
做法很简单，对给出的多边形求一次凸包，然后将原多边形的顶点顺序倒序（这是因为我的凸包是逆时针构建的），然后对齐凸包上的第一个点（一定存在能被对其的顶点，阴为在凸包上的点都在原多边形上）。然后从这个点开始扫描，如果凸包上两个点是相邻的，同时这两个点在原多边形上也是相邻的，那么这两个点之间那条边就是凸包上的边，否则就有一个缺失了的区域了。
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 8 using namespace std; 9 10 struct Point { 11 int x, y; 12 Point() {} 13 Point(int x, int y) : x(x), y(y) {} 14 } ; 15 bool operator < (Point x, Point y) { return x.x - y.x < 0 || x.x - y.x == 0 && x.y - y.y < 0;} 16 bool operator == (Point x, Point y) { return x.x - y.x == 0 && x.y - y.y == 0;} 17 Point operator + (Point x, Point y) { return Point(x.x + y.x, x.y + y.y);} 18 Point operator - (Point x, Point y) { return Point(x.x - y.x, x.y - y.y);} 19 20 inline int crossDet(Point a, Point b) { return a.x * b.y - a.y * b.x;} 21 inline int crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);} 22 inline int dotDet(Point a, Point b) { return a.x * b.x + a.y * b.y;} 23 24 int andrew(Point *pt, int n, Point *ch) { 25 sort(pt, pt + n); 26 int m = 0; 27 for (int i = 0; i < n; i++) { 28 while (m > 1 && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--; 29 ch[m++] = pt[i]; 30 } 31 int k = m; 32 for (int i = n - 2; i >= 0; i--) { 33 while (m > k && crossDet(ch[m - 2], ch[m - 1], pt[i]) <= 0) m--; 34 ch[m++] = pt[i]; 35 } 36 if (n > 1) m--; 37 return m; 38 } 39 40 const int N = 55; 41 Point pt[N], ch[N], tmp[N]; 42 43 int main() { 44 // freopen("in", "r", stdin); 45 int p, q, n, T; 46 cin >> T; 47 while (T-- && cin >> p >> q >> n) { 48 for (int i = 0; i < n; i++) { cin >> pt[i].x >> pt[i].y; tmp[i] = pt[i];} 49 int m = andrew(tmp, n, ch); 50 reverse(pt, pt + n); // 反向原多边形 51 while (!(pt[0] == ch[0])) rotate(pt, pt + 1, pt + n); // 对齐其始点 52 pt[n] = pt[0], ch[m] = ch[0]; 53 // for (int i = 0; i < m; i++) cout << ch[i].x << ' ' << ch[i].y << endl; 54 // puts("~~~~~"); 55 // for (int i = 0; i < n; i++) cout << pt[i].x << ' ' << pt[i].y << endl; 56 // puts("!!!!!"); 57 int dents = 0, faces = 0; 58 for (int i = 1, j = 1; i <= m; i++) { // 凸包上的顶点顺序枚举一次，统计出结果 59 while (!(ch[i] == pt[j])) j++; 60 if (ch[i - 1] == pt[j - 1]) faces++; 61 else dents++; 62 } 63 cout << max(0, - dents * p + faces * q) << endl; 64 } 65 return 0; 66 }
——written by Lyon