最近兩次比賽出現兩道相同類型的題，有人十幾分鐘就AC了，而有人卡了倆小時。。。反思。。

?

?先說hdu4353這道題，題意是要求一個從N個點1里邊畫出一個多邊形來，然后給出M個點2。讓這個（多邊形的面積/多邊形內點2的個數）最小。

?描述很復雜。。。但是仔細想想會發現，多邊形的點越多，面積也就越大，所以，這里只能畫三個點，也就是一個三角形。至于怎么求點2的個數，這是很有必要總結的，祭奠我那苦逼的倆小時吧。。。。

先看一個圖：?

這不是立體圖，僅僅是個平面圖。。。

假設sum[i][j]表示i，j這條線上方這塊區域的點的數目

可以看到三角形內點2的數目 = sum[i][j] + sum[j][k] - sum[i][k]；

其實更通用一點就是： abs(sum[i][k] - sum[i][j] - sum[j][k]);

既然統計出這些點數來，這個問題基本就解決了。

?HDU 4353的代碼：

View Code const int N = 210; const int M = 511;struct Point {int x, y;bool operator < (const Point& cmp) const {return x < cmp.x;} };Point a[N], b[M]; int sum[N][N]; int n, m;inline int det(int x1, int y1, int x2, int y2) {return x1*y2 - x2*y1; }inline int cross(Point a, Point b, Point c) {return det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y); }int main() {//freopen("data.in", "r", stdin);int i, j, k, t, cas = 0, cnt;double ans, area;scanf("%d", &t);while(t--) {scanf("%d%d", &n, &m);REP(i, n) scanf("%d%d", &a[i].x, &a[i].y);REP(i, m) scanf("%d%d", &b[i].x, &b[i].y);sort(a, a + n);for(i = 0; i < n; ++i) {for(j = i + 1; j < n; ++j) {sum[i][j] = 0;for(k = 0; k < m; ++k) {if(b[k].x >= a[i].x && b[k].x < a[j].x) {if(cross(a[i], a[j], b[k]) > 0) sum[i][j]++;}}}}ans = -1;for(i = 0; i < n; ++i) {for(j = i + 1; j < n; ++j) {for(k = j + 1; k < n; ++k) {cnt = sum[i][k] - sum[i][j] - sum[j][k];if(cnt == 0) continue;area = double(cross(a[i], a[j], a[k]))/2;if(ans == -1 || fabs(area/cnt) < ans) ans = fabs(area/cnt);}}}if(ans == -1) printf("Case #%d: -1\n", ++cas);else printf("Case #%d: %.6lf\n", ++cas, ans);}return 0; }

?

? 還有一個就是多校9上的1001題（HDU 4380）。比上面這個題更直白，需要統計三角形內的點數是不是奇數就可以。。。

?

?　　

轉載于:https://www.cnblogs.com/vongang/archive/2012/08/22/2650887.html

總結

以上是生活随笔為你收集整理的关于多边形内点数问题的一些变形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。