自动搬运

查看原文

来自洛谷，原作者为

	Thronf Accessor

搬运于2025-08-24 21:23:31，当前版本为作者最后更新于2024-07-20 11:51:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻的第一篇题解。

推导

首先，对于本题，很显然正方形都在第一象限，那么，可以用直线去模拟每一条“视线”。

你可以理解为固定你的坐标 $(0,0)$ ，同时转头，从 $x$ 轴逆时针转到 $y$ 轴。

然后对于每一根直线，通过区间判断来找出每条直线所“接触”的第一个正方形（这就需要你进行排序），把正方形打上标记（用结构体就可以搞定），最后用一个量来统计数量。

最后输出答案。

几个问题（dalao 跳过）

1. 排序关键字

   这道题的调式点在于排序和精度，而排序又是比较难想到的，主要有以下两种错误排序：

• 顶点排序

  以左下角顶点为关键字，比较该点到 $O$ 点的距离，从小到大排序。 $(70pts)$

• 斜线排序

  以 $X+Y$ 为关键字进行排序。 $(80pts)$

显然，前面两组排序方式较为片面，所以，综合多方面考虑，那么最显而易见的就是以 $X+Y+L$ 进行排序。

2. 精度选择

   对于查找间隔，很多同志可能会先以斜率为查找对象，然而并不行，因为这样的话，对于与 $x$ 轴夹角小于 $\frac{\pi}{4}$ 的直线间隔太大，而大于 $\frac{\pi}{4}$ 的直线又间隔太小，如果要达到要求的精度 $(\frac{1}{10000},10000)$ 就一定会 TLE ，所以考虑用角度作为查找对象。这个精度大家要慢慢去找，我这里有个参考值是 $\frac{\pi}{180000}$ 。

附上代码

#include<bits/stdc++.h>
#define int long long // 防止忘记开long long 
//#define for(i,a,b,c,d) for(int i=a;i d b;i+=c)
using namespace std;
const double pi=3.141592653589793238462643383279502884197169399375105; // 圆周率 
struct sqare{
   double x1,y1,x2,y2;
   bool can;
}a[10005]; // 存储正方形（ can 用来打标记） 
int n,ans;
int check(int i,double k) // 判断是否经过正方形 
{
   if(a[i].x1*k<a[i].y2&&(a[i].x2*k>a[i].y1)) // 自己画图像 
   {
   	if(!a[i].can)
   	{
   		a[i].can=1;
   		return 1;
   	}
   	else
   		return 2; // 如果已经有了隔挡的正方形 
   }
   return 0;
}
bool cmp(sqare a,sqare b) // 排序用
{
   return (a.x1+a.y2)<(b.x1+b.y2);
}
signed main() // 用了 #define int long long 就不能再用int main（）了 
{
   ios::sync_with_stdio(0); // 关缓冲区 
   cin>>n;
   for(int i=1;i<=n;i++)
   {
   	double x,y,l; // 输入 
   	cin>>x>>y>>l;
   	a[i].x1=x,a[i].x2=x+l,a[i].y1=y,a[i].y2=y+l;
   }
   sort(a+1,a+1+n,cmp); // 排序 
   for(double thita=pi/180000;thita<pi/2;thita+=pi/180000) // 枚举角度 
   {
   	double k=tan(thita); // 算斜率 
   	for(int i=1;i<=n;i++)
   	{
   		int c=check(i,k);
   		if(c==1)
   		{
   			ans++;
   			break;
   		}
   		else if(c==2)
   			break;
   	}
   }
   cout<<ans; 
   return 0; 
}