本題主要是確定給定的點在那塊區域。原題給出n條直線，將長方形分為n+1快區域。我們可以對每個給定的點來判斷它在那塊區域，判段方法可以根據點與直線的位置關系，具體如下，對于點（x0,y0）和直線ax+by+c=0(a>0):

? ? ?1)若a*x0+b*y0+c=0,則點在直線上。

? ? ?2)若a*x0+b*y0+c>0,則點在直線右側。

? ? ?3)若a*x0+b*y0+c<0,則點在直線左側。

順序查找點的位置必然會耗費大量的時間。所以采用二分方法，找到點所在的區間，然后累計起來。下面代碼將ax+by+c=0化簡為x+(b/a)y+(c/a)=0,默認x的系數為1.

#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<string> #include<queue> #include<cmath> #include<string.h> #include<algorithm> #include<vector> using namespace std; const int MAXN = 5001; struct Line{double b, c; //x+b*y+c=0 }; Line L[MAXN]; int Count[MAXN]; int BinFind(int x,int y,int n); int main(){int x1, y1, x2, y2,s,t,n,m,i,x,y,id,c=1;while (scanf("%d", &n)&&n){if (c != 1) //控制下格式cout << endl;c++;scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);memset(Count, 0, sizeof(Count));L[0].b = 0, L[0].c = 0 - x1; //第一條直線應該是矩形左邊的一條邊for (i = 0; i < n; i++){scanf("%d%d", &s, &t);L[i+1].b = (t - s)*1.0/(y1 - y2);L[i+1].c = (y2*s - t*y1)*1.0 / (y1 - y2);}L[n + 1].b = 0, L[n + 1].c = 0 - x2; //最后一條直線應該是矩形右邊那條邊for (i = 0; i < m; i++){scanf("%d%d", &x, &y);id = BinFind(x, y, n);Count[id]++;}for (i = 0; i <= n; i++)cout << i << ": " << Count[i] << endl;}return 0; } int BinFind(int x, int y,int n){int left = 0, right = n+1; while (left < right-1){ //找到的點在區間(L[left],L[rigth])之間int mid = (left + right) >> 1;if (x + L[mid].b*y + L[mid].c>0) //點在直線右邊left = mid;elseright = mid;}return left; }

　　

轉載于:https://www.cnblogs.com/td15980891505/p/5686621.html

總結

以上是生活随笔為你收集整理的TOYS-POJ2318的全部內容，希望文章能夠幫你解決所遇到的問題。

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