poj 2398 Toy Storage (计算几何,判断点和线段关系)

Jul 21, 2015 · 3 min read · 计算几何

题意大概是说将一个盒子用n个board分成n+1 部分

然后往里面放toy,给定盒子,board,和toy的坐标

问所有的toy放完后,有多少部分中有t个toy;

简单计算几何

需要判断的是点和直线的关系.

判断某一点在直线左右侧

左右方向是相对前进方向的,只要指定了前进方向就可以知道左右(比如指定前进方向是从直线的起点到终点).判断点在直线的左侧还是右侧是计算几何里面的一个最基本算法.使用矢量来判断.
定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：

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

当P1P2P3逆时针时S为正的，当P1P2P3顺时针时S为负的。

令矢量的起点为A，终点为B，判断的点为C，
如果S（A，B，C）为正数，则C在矢量AB的左侧；
如果S（A，B，C）为负数，则C在矢量AB的右侧；
如果S（A，B，C）为0，则C在直线AB上。**

  1
  2
  3 
  4
  5    
  6    /*************************************************************************
  7    	> File Name: code/poj/2398.cpp
  8    	> Author: 111qqz
  9    	> Email: rkz2013@126.com 
 10    	> Created Time: 2015年11月08日 星期日 10时04分32秒
 11     ************************************************************************/
 12    #include<iostream>
 13    #include<iomanip>
 14    #include<cstdio>
 15    #include<algorithm>
 16    #include<cmath>
 17    #include<cstring>
 18    #include<string>
 19    #include<map>
 20    #include<set>
 21    #include<queue>
 22    #include<vector>
 23    #include<stack>
 24    using namespace std;
 25    #define REP(i, n) for (int i=0;i<int(n);++i)  
 26    typedef long long LL;
 27    typedef unsigned long long ULL;
 28    const int N=2E3+5;
 29    struct node
 30    {
 31        int x,y;
 32    };
 33    struct node rec,rec2;
 34    struct node par[N],par2[N];
 35    struct node toy[N];
 36    int ans[N],cnt[N];
 37    int n,m;
 38    bool judge(node p1,node p2,node p3) //判断点是否在直线的[右侧!!]
 39    {
 40        int s = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);
 41        if (s>0) return false;
 42        if (s<0) return true;
 43    }
 44    bool cmp(node a,node b)
 45    {
 46        if (a.x<b.x) return true;
 47        if (a.x==b.x&&a.y<b.y) return true;
 48        return false;
 49    }
 50    int main()
 51    {
 52       // freopen("in.txt","r",stdin);
 53        while (scanf("%d",&n)!=EOF&&n)
 54        {
 55    	  memset(ans,0,sizeof(ans));
 56    	  memset(par,0,sizeof(par));
 57    	  memset(par2,0,sizeof(par2));
 58    	  memset(toy,0,sizeof(toy));
 59    	  cin>>m>>rec.x>>rec.y>>rec2.x>>rec2.y;
 60    	  for ( int i = 1 ;  i <= n ; i++)
 61    	  {
 62    		cin>>par[i].x>>par2[i].x;
 63    		par[i].y=rec.y;
 64    		par2[i].y=rec2.y;
 65    	  }
 66    	  for ( int i = 1 ; i <= n-1 ; i++)
 67    	  {
 68    		for ( int j = i+1 ; j <= n ; j++)
 69    		{
 70    		    if (par[i].x>par[j].x)
 71    		    {
 72    			  swap(par[i].x,par[j].x);
 73    		    //  swap(par[i].y,par[j].y);
 74    			  swap(par2[i].x,par2[j].x);
 75    		    //   swap(par2[i].y,par2[j].y);
 76    		    }
 77    		}
 78    	  }
 79    //	  for ( int i = 1 ;  i <= n ; i++)
 80    //		cout<<par[i].x<<endl;
 81    	  for ( int i = 1 ;  i <= m ; i++ )
 82    	   {
 83    		cin>>toy[i].x>>toy[i].y;
 84    	   }
 85    	  int p;
 86    	  sort(toy+1,toy+m+1,cmp);  //如果第i个娃娃在第k个分划中,那么排序后第i+1个娃娃至少在第k个分划中....(某大神说过,顺手就能写的优化顺手	
 87    //	  for ( int i = 1 ; i <= m ; i++)  cout<<"x[i]:"<<toy[i].x<<" y[i]:"<<toy[i].y<<endl;
 88    	  for ( int i = 1 ; i  <= m ;  i++) 
 89    	  {
 90    		p = n + 1;  //如果在所有board的右侧,那么一定是在最后一个分划中(n个板子形成n+1个分划)
 91    		bool ok=false;
 92    		for ( int j = 1 ; j  <= n ; j++)
 93    		{
 94    		    ok=judge(par2[j],par[j],toy[i]);
 95    		    if (!ok)
 96    		    {
 97    		//	  cout<<"i:"<<i<<" j:"<<j<<" "<<par2[j].x<<" "<<par2[j].y<<" "<<par[j].x<<" "<<par[j].y<<endl;
 98    			  p = j;
 99    			  break;
100    			//    cout<< "hhhhhh"<<"I:"<<i<<" j:"<<j<<endl;
101    		    }
102    		}
103    		ans[p]++;
104    	  }
105    	  cout<<"Box"<<endl;
106    	  memset(cnt,0,sizeof(cnt));
107    	  for ( int i = 1 ; i <= n+1 ; i++)
108    	  {
109    		if (ans[i]==0) continue;
110    		cnt[ans[i]]++;
111    //		printf("%d: %d\n",i-1,ans[i]);
112    	  } 
113    //	  puts("");
114    	  for ( int i = 1 ; i <= m ;  i++)
115    	  {
116    		if (cnt[i]==0) continue;
117    	  	printf("%d: %d\n",i,cnt[i]);
118    	  }
119        }
120        return 0;
121    }
122    
123