http://poj.org/problem?id=2398

題意大概是說(shuō)將一個(gè)盒子用n個(gè)board分成n+1 部分

然后往里面放toy,給定盒子,board,和toy的坐標(biāo)

問(wèn)所有的toy放完后,有多少部分中有t個(gè)toy;

簡(jiǎn)單計(jì)算幾何

需要判斷的是點(diǎn)和直線的關(guān)系.

判斷 某一點(diǎn)在直線左右側(cè)

左右方向是相對(duì)前進(jìn)方向的,只要指定了前進(jìn)方向就可以知道左右(比如指定前進(jìn)方向是從直線的起點(diǎn)到終點(diǎn)).判斷點(diǎn)在直線的左側(cè)還是右側(cè)是計(jì)算幾何里面的一個(gè)最基本算法.使用矢量來(lái)判斷.?
定義：平面上的三點(diǎn)P1(x1,y1),P2(x2,y2),P3(x3,y3)的面積量：

S(P1,P2,P3)=|y1 y2 y3|= (x1-x3)*(y2-y3)-(y1-y3)*(x2-x3)?

當(dāng)P1P2P3逆時(shí)針時(shí)S為正的，當(dāng)P1P2P3順時(shí)針時(shí)S為負(fù)的。?

令矢量的起點(diǎn)為A，終點(diǎn)為B，判斷的點(diǎn)為C，?
如果S（A，B，C）為正數(shù)，則C在矢量AB的左側(cè)；?
如果S（A，B，C）為負(fù)數(shù)，則C在矢量AB的右側(cè)；?
如果S（A，B，C）為0，則C在直線AB上。

?

/*************************************************************************> File Name: code/2015summer/0718/B.cpp> Author: 111qqz> Email: rkz2013@126.com > Created Time: 2015年07月18日 星期六 11時(shí)58分14秒************************************************************************/ #include<iostream> #include<iomanip> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<map> #include<set> #include<queue> #include<vector> #include<stack> using namespace std; #define REP(i, n) for (int i=0;i<int(n);++i) typedef long long LL; typedef unsigned long long ULL; const int N=2E3+5; struct node {int x,y; }; struct node rec,rec2; struct node par[N],par2[N]; struct node toy[N]; int ans[N],cnt[N]; int n,m; bool judge(node p1,node p2,node p3) //判斷點(diǎn)是否在直線的[右側(cè)!!] {int s = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);if (s>0) return false;if (s<0) return true; } bool cmp(node a,node b) {if (a.x<b.x) return true;if (a.x==b.x&&a.y<b.y) return true;return false; } int main() {while (scanf("%d",&n)!=EOF&&n){memset(ans,0,sizeof(ans));memset(par,0,sizeof(par));memset(par2,0,sizeof(par2));memset(toy,0,sizeof(toy));cin>>m>>rec.x>>rec.y>>rec2.x>>rec2.y;for ( int i = 1 ; i <= n ; i++){cin>>par[i].x>>par2[i].x;par[i].y=rec.y;par2[i].y=rec2.y;}for ( int i = 1 ; i <= n-1 ; i++){for ( int j = i+1 ; j <= n ; j++){if (par[i].x>par[j].x){swap(par[i].x,par[j].x);// swap(par[i].y,par[j].y); swap(par2[i].x,par2[j].x);// swap(par2[i].y,par2[j].y); }}} // for ( int i = 1 ; i <= n ; i++) // cout<<par[i].x<<endl;for ( int i = 1 ; i <= m ; i++ ){cin>>toy[i].x>>toy[i].y;}int p;sort(toy+1,toy+m+1,cmp); //如果第i個(gè)娃娃在第k個(gè)分劃中,那么排序后第i+1個(gè)娃娃至少在第k個(gè)分劃中....(某大神說(shuō)過(guò),順手就能寫(xiě)的優(yōu)化順手 // for ( int i = 1 ; i <= m ; i++) cout<<"x[i]:"<<toy[i].x<<" y[i]:"<<toy[i].y<<endl;for ( int i = 1 ; i <= m ; i++) {p = n + 1; //如果在所有board的右側(cè),那么一定是在最后一個(gè)分劃中(n個(gè)板子形成n+1個(gè)分劃)bool ok=false;for ( int j = 1 ; j <= n ; j++){ok=judge(par2[j],par[j],toy[i]);if (!ok){// cout<<"i:"<<i<<" j:"<<j<<" "<<par2[j].x<<" "<<par2[j].y<<" "<<par[j].x<<" "<<par[j].y<<endl;p = j;break;// cout<< "hhhhhh"<<"I:"<<i<<" j:"<<j<<endl; }}ans[p]++;}cout<<"Box"<<endl;memset(cnt,0,sizeof(cnt));for ( int i = 1 ; i <= n+1 ; i++){if (ans[i]==0) continue;cnt[ans[i]]++;// printf("%d: %d\n",i,ans[i]); }for ( int i = 1 ; i <= m ; i++){if (cnt[i]==0) continue;printf("%d: %d\n",i,cnt[i]);}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/111qqz/p/4665640.html

總結(jié)

以上是生活随笔為你收集整理的poj 2398 Toy Storage (计算几何,判断点和线段关系)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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