題意：同POJ2318

#include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; struct point {int x, y; }; struct Node {point Low, High; }line[5010];int Num[5010]; int par[5010]; bool cmp(Node A, Node B) {return A.High.x < B.High.x; }bool is_right(int x, int y, Node ln) {point P = ln.High;point Q = ln.Low;if (((P.x - x)*(Q.y - y) - (P.y - y)*(Q.x - x)) > 0)return true;elsereturn false; }void bin_seach(int x, int y, int n) {int left = 1;int right = n;while (left <= right) {int mid = (left + right) / 2;if (is_right(x, y, line[mid])) {left = mid + 1;}else {right = mid - 1;}}par[left]++;} int main() {int n, m, i, j, x1, x2, y1, y2;while (scanf("%d", &n), n) {memset(par, 0, sizeof(par));memset(Num, 0, sizeof(Num));scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);for (int i = 1; i <= n; i++) {scanf("%d", &line[i].High.x);line[i].High.y = y1;scanf("%d", &line[i].Low.x);line[i].Low.y = y2;}sort(line + 1, line + 1 + n, cmp);int xx, yy;int t = m;while (m--) {scanf("%d%d", &xx, &yy);bin_seach(xx, yy, n);}for (int i = 1; i <= n + 1; i++) {if (par[i])Num[par[i]]++;}printf("Box\n");for (int i = 1; i <= t; i++) {if (Num[i])printf("%d: %d\n", i, Num[i]);}}return 0; }

轉載于:https://www.cnblogs.com/tennant/p/8758580.html

總結

以上是生活随笔為你收集整理的POJ2398【判断点在直线哪一侧+二分查找区间】的全部內容，希望文章能夠幫你解決所遇到的問題。

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