2015年ALPC暑期專題練習I （計算幾何） A

久違的1A，爽！

題目大意：根據玩具的坐标，得到每個硬紙闆中有幾個玩具。

思路：先對線進行排序，得到每個分片的id，然後逐個判斷玩具在哪條線的左邊，即可得到id。主要是點和線類的構造函數與拷貝函數。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
//#include<cmath>
using namespace std;
int min_2 (int& a,int& b){return a<b?a:b;}
int max_2 (int& a,int& b){return a>b?a:b;}

const int MAX_NUM = 5000+10;
struct point{
  int x,y;
  point (int i,int j){
	x=i;y=j;
  }
  point (const point& p){
	x=p.x;y=p.y;
  }
  point& operator = (const point& p){
	x=p.x;y=p.y;
	return *this;
  }
  point (){}
};
struct line : point{
  point x,y;
  line (point i,point j){
	x=i;y=j;
  }
  line (){}
};
line lineSet[MAX_NUM];
struct polygon : point{
  point ul,ll,lr,ur;
}polygonSet[MAX_NUM];

int n,m,x1,y1,x2,y2;
int toyNum[MAX_NUM];

bool cmp (line l,line r)
{
  int ll=min_2 (l.x.x,l.y.x);
  int lr=min_2 (r.x.x,r.y.x);
  return ll<lr;
}
int CrossMuti (point a,point b)
{
  return a.x*b.y-a.y*b.x;
}
int JudgePointDirWithLine (point& x,int id) {
  point ac (x.x-lineSet[id].x.x , x.y-lineSet[id].x.y);
  point ab (lineSet[id].y.x-lineSet[id].x.x , lineSet[id].y.y-lineSet[id].x.y);
  if (CrossMuti (ac,ab)<0)//x int id right
	return 1;
  else if (CrossMuti (ac,ab)>0)//x int id lift
	return 2;
  else return 0;//error
}

int main()
{
  while (scanf ("%d",&n) && n)
  {
	scanf ("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
	memset (toyNum,0,sizeof (toyNum));
	int ui,li;
	for (int i=1;i<=n;i++){
	  scanf ("%d %d",&ui,&li);
	  lineSet[i].x=point (ui,y1);
	  lineSet[i].y=point (li,y2);
	}
	lineSet[0].x=point (x1,y1);
	lineSet[0].y=point (x1,y2);
	lineSet[n+1].x=point (x2,y1);
	lineSet[n+1].y=point (x2,y2);
	sort (lineSet,lineSet+n+2,cmp);
	/*for (int i=0;i<n+2;i++)
	  printf ("%d ",lineSet[i].y.x);
	printf ("\n");*/
	
	point toy;
	for (int i=0;i<m;i++){
	  scanf ("%d %d",&toy.x,&toy.y);
	  for (int j=0;j<n+2;j++){
		if (JudgePointDirWithLine (toy,j)==2){
		  ++toyNum[j-1];
		  break;
		}
	  }
	}
	for (int i=0;i<=n;i++)
	  printf ("%d: %d\n",i,toyNum[i]);
	printf ("\n");
	
  }
  return 0;
}