A - TOYS POJ - 2318

題意：

一個盒子中有n個隔板，分出n+1個空間（從左往右空間的編號分別是0…n），（隔板之間不會相交，且按照從左往右的順序給出），現(xiàn)在給你m個坐標(biāo)的物品，問盒子每個空間內(nèi)有多少物品

題解：

本質(zhì)就是判斷點(diǎn)在直線的哪一側(cè)
我們設(shè)直線為：x+by+c=0
給一個坐標(biāo)(x0,y0)
如果x0+by0+c = 0說明在直線上（題目數(shù)據(jù)不可能出現(xiàn)在直線上）
如果x0+by0+c>0,說明點(diǎn)在直線的右側(cè)
如果x0+by0+c<0,說明點(diǎn)在直線的左側(cè)
因?yàn)轭}目給的直線是按照順序排好的，所謂我們可以二分查找點(diǎn)所在直線的區(qū)域
b和c如何得到？看下圖推導(dǎo)

代碼：

#include<iostream> #include<string> #include<queue> #include<cmath> #include<string.h> #include<algorithm> #include<vector> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=5e3+1; struct Line{double c,b;/*x+by+c=0;*/ }L[maxn]; int cou[maxn]; int Find(int x,int y,int n){int l=0,r=n+1;while(l<r-1){//找到的點(diǎn)在區(qū)間（L[left],L[right]）之間 int mid=(l+r)>>1;if(x+L[mid].b*y+L[mid].c>0)//該點(diǎn)在直線的右側(cè)l=mid;else r=mid;}return l; } int main() {int n,m,x1,y1,x2,y2;//n是隔板數(shù)量，m是玩具數(shù)量 int c=1;while(cin>>n&&n){ // if(c!=1)cout<<endl; // c++;cin>>m>>x1>>y1>>x2>>y2;memset(cou,0,sizeof(cou));L[0].b=0;L[0].c=0-x1;int u,l;for(int i=1;i<=n;i++){cin>>u>>l;L[i].b=(double)(l-u)/(double)(y1-y2);L[i].c=-1.0*L[i].b*y1-1.0*u;}L[n+1].b=0;L[n+1].c=0-x2;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;int id=Find(x,y,n);cou[id]++;}for(int i=0;i<=n;i++){printf("%d: %d\n",i,cou[i]);}cout<<endl;}return 0; }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。