題意：將m個玩具扔進一個從左到右分成n個塊的箱子中，問每個分塊裡有多少個玩具（箱子的左上角坐標為(x1, y1)，箱子右下角坐標為(x2, y2)，中間n條分隔欄的上坐標的橫坐標為U[i]，下坐標的橫坐標為L[i]）。 ——>>人生第一道ACM幾何題目！翻了一下白書加強版——汝佳的《訓練指南》，恰恰有判斷點在多邊形內的方法——轉角法，寫上submit，處理不好，得了個TLE，Google一下，看到了“二分”這個字眼，立馬回到自己的代碼，將原來的兩個for尋找點的位置換成二分分塊尋找點的位置（用叉積判斷點在目前探尋邊的左邊還是右邊），submit，這次得了個PE，回看題目：“Separate the output of different problems by a single blank line.”，難道說最後一組數據也要空行（其實已經可以肯定），再改，125MS——AC！ [cpp] www.2cto.com #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int maxn = 5000 + 10; //0 < n <= 5000, 0 < m <= 5000 const double eps = 1e-10; //為了精度 int cnt[maxn]; //各個分塊的玩具數量 struct Point //點數據類型 { double x, y; Point(double x = 0, double y = 0):x(x), y(y){} }; typedef Point Vector; //引用為向量類型 Vector operator - (Vector A, Vector B) //重載-運算符 { return Vector(A.x-B.x, A.y-B.y); } int dcmp(double x) //為了精度 { if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } double Cross(Vector A, Vector B) //叉積函數 { return A.x*B.y - A.y*B.x; } Vector U[maxn], L[maxn]; //輸入的上部點與下部點 int main() { int n, m, i; double x1, y1, x2, y2; while(~scanf("%d", &n)) { if(!n) return 0; scanf("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2); for(i = 1; i <= n; i++) //將箱子的左端存了U[0]與L[0]，故輸入的邊從1開始 { scanf("%lf%lf", &U[i].x, &L[i].x); U[i].y = y1; L[i].y = y2; } U[0].x = x1; U[0].y = y1; //箱子左端 L[0].x = x1; L[0].y = y2; U[n+1].x = x2; U[n+1].y = y1; //箱子右端 L[n+1].x = x2; L[n+1].y = y2; memset(cnt, 0, sizeof(cnt)); //初始化 Point p; for(i = 1; i <= m; i++) { scanf("%lf%lf", &p.x, &p.y); int l = 0, r = n+1; //二分確定位置 while(l < r) { int M = l + (r - l) / 2; if(dcmp(Cross(U[M]-L[M], p-L[M])) > 0) r = M; else l = M+1; } cnt[l-1]++; } for(i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]); printf("\n"); //氣！開始理解為最後一組不用空行，PE了一次 } return 0; }
