Poj 2398 Toy Storage (叉积+二分)

一时失言乱红尘 2023-01-17 07:38 167阅读 0赞

第一道用codeblocks敲的题，在换行缩进等方面还不是很适应，居然没有变量名整体替换功能。。。。

变量名字长些可以用查找+替换，短了基本无解。。。

这一题和上一题基本一样，只不过板子没有按照顺序给出，需要排序。最后要求输出包含同样个数的玩具的格子各有多少个

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=1005;
    int n,m,x1,y11,x2,y2;
    int cnt[N],ans[N];
    
    template<typename Type>
    class Point
    {
    public:
    	Type x,y;
    
    	Point(){}
    	Point (Type _x,Type _y)
    	{
    		x=_x;
    		y=_y;
    	}
    	Point operator-(const Point &b) const
    	{
    		return Point(x-b.x,y-b.y);
    	}
    	//调用点a的该函数
    	//返回正值点a在向量bc的左侧
    	//返回负值点a在向量bc的右侧
    	//返回0点a在向量bc这条直线上
    	Type Cross (Point b,Point c)
    	{return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y);}
    };
    
    struct Line
    {
        Point<int> up,down;
        bool operator < (const Line& b) const
        {
            return up.x<b.up.x;
        }
    }line[N];
    
    Point<int> data[N];
    
    void Init ()
    {
    	int i,a,b;
    	memset(cnt,0,sizeof(cnt));
    	memset(ans,0,sizeof(ans));
    	for (i=0;i<n;i++)
    	{
    		scanf("%d%d",&a,&b);
    		line[i].up=Point<int>(a,y11);
    		line[i].down=Point<int>(b,y2);
    	}
    	sort(line,line+n);     //此题板子需要排序
    	for (i=1;i<=m;i++)
    	{
    		scanf("%d%d",&a,&b);
    		data[i]=Point<int>(a,b);
    	}
    }
    
    int Solve (Point<int> cc)
    {
    	int low=0,high=n,mid;
    	while (low<=high)
    	{
    		mid=(low+high)>>1;
    		if (line[mid].down.Cross(line[mid].up,cc)>0)
    			high=mid-1;
    		else
    			low=mid+1;
    	}
    	if (low>n) low=n;
    	return low;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	while (scanf("%d",&n),n)
    	{
    		scanf("%d%d%d%d%d",&m,&x1,&y11,&x2,&y2);
    		int i;
    		Init ();
    		for (i=1;i<=m;i++)
    			cnt[Solve(data[i])]++;
            printf("Box\n");
    		for (i=0;i<=n;i++)
                ans[cnt[i]]++;
            for (i=1;i<=n;i++)
                if (ans[i])
                    printf("%d: %d\n",i,ans[i]);
    	}
    	return 0;
    }