代码求调，思路求hack

link

前言

这是一个准题解，因为我的代码仍没有AC

可以认为这篇博客只是讲述了一个思路

正文

思想——降维

这本是物理学中的一个名词，指通过改变参考系的方法使所有物体的运动变得更加简洁

其中地心说改日心说就是一个典型的例子，地心说中其他行星的运动都非常复杂，而以太阳为中心（最起码对于太阳系）运动则简单的很多

正正文

我们看会题目，发现云有两种运动方向，觉得非常的复杂

所以可以考虑让坐标系原点也以 $1$ 个单位每秒的速度往移动

这样向上的云就不动了，向右的又会向下移动

此时没学过矢量的人都能想到，本来向右的现在会以右下 $45$° 的方向移动

所以现在只有不动的云和右下运动的云

因为在0时刻所有云互不相交，因此所有水平运动的云互不相交，并且所有竖直的云也是互不相交的，所以同一个点最多被两朵云覆盖，而且一个是水平运动的另一个是竖直运动的云，所以答案要么是1要么是2对应着是否出现过云相交的情况

可以将一个向右下移动的云的轨迹表示为其左下和右上的顶点所形成的两条斜率为 $-1$ 的直线

而将不动的云的左下和右上的顶点所形成的两条斜率为 $-1$ 的直线

表示会与其发生堆叠的点的轨迹范围

然后考虑两个云的轨迹交叠情况即可

当然时间是过不去的，所以考虑将两类云按照右上顶点的直线方程的零次项（即 $y=kx + b$ 的 $b$）从大到小排序

然后同时遍历右下移动的云和不动的云

Coding

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int T,n;
int _x[maxn],_y[maxn],_w[maxn],_h[maxn],_d[maxn];
int cnt1,cnt2;

struct segment
{
	int x0,y0,x,y;
}seg1[maxn],seg2[maxn];

bool cmp(segment a,segment b)
{
	return a.x + a.y > b.x + b.y;
}

int main()
{
    cin >> T;
    while(T--)
    {
    	cnt1 = cnt2 = 0;
    	cin >> n;
    	for(int i = 1;i <= n;i++)
    	{
    		cin >> _x[i] >> _y[i] >> _w[i] >> _h[i] >> _d[i];
    		if(_w[i] < 0)
    		{
    			_x[i] += _w[i];
    			_w[i] = -_w[i];
			}
			if(_h[i] < 0)
    		{
    			_y[i] += _h[i];
    			_h[i] = -_h[i];
			}
    		if(!_d[i])
    		{
    			seg2[++cnt2].x0 = _x[i];
				seg2[cnt2].y0 = _y[i];
				seg2[cnt2].x = _x[i] + _w[i];
				seg2[cnt2].y = _y[i] + _h[i];
			}
    		else
    		{
    			seg1[++cnt1].x0 = _x[i];
				seg1[cnt1].y0 = _y[i];
				seg1[cnt1].x = _x[i] + _w[i];
				seg1[cnt1].y = _y[i] + _h[i];
			}
		}
		sort(seg1 + 1,seg1 + cnt1 + 1,cmp);
		sort(seg2 + 1,seg2 + cnt2 + 1,cmp);
		for(int i = 1,j = 1;i <= cnt2,j <= cnt1;i++)
		{
			while(seg1[j].x + seg1[j].y > seg2[i].x0 + seg2[i].y0)
			{
				if(j > cnt1)
				{
					cout << 1 << endl;
					goto Next;
				}
//				cout << j << " wewe\n";
				if(seg2[i].x0 + seg2[i].y0 > seg1[j].x0 + seg1[j].y0 and seg2[i].x0 + seg2[i].y0 < seg1[j].x + seg1[j].y)
				{
					cout << 2 << endl;
					goto Next;
				}
				if(seg2[i].x + seg2[i].y > seg1[j].x0 + seg1[j].y0 and seg2[i].x + seg2[i].y < seg1[j].x + seg1[j].y)
				{
					cout << 2 << endl;
					goto Next;
				}
				if(seg2[i].x0 + seg2[i].y0 <= seg1[j].x0 + seg1[j].y0 and seg2[i].x + seg2[i].y >= seg1[j].x + seg1[j].y)
				{
					cout << 2 << endl;
					goto Next;
				}
				j++;
			}
		}
		cout << 1 << endl;
		Next:;
	}
    return 0;
}