Poj Kadj Squares（几何）

Kadj Squares

题意 给N个正方形的边长，沿着左下顶点逆时针旋转45度放置，此时一顶点在x轴上。第一个正方形的一顶点在y轴上，从左向右一次放置，允许边重合但不允许面积相交，求那些正方形从上往下看时可以被看到。

思路 一开始我是先求出来b的坐标，进而知道左右端点的坐标，然后判断举矩形是否被覆盖，不知道是写错了还是被卡了精度。后来发现我们可以将边长扩大$\sqrt{2}$倍，这时求的左右端点就都是整数了。然后根据左右端点判断是否被覆盖即可。

代码

#pragma GCC optimize(2) //#include<bits/stdc++.h> #include<iostream> #include<cstdio> //#include<cmath> using namespace std; typedef long long ll; typedef unsigned long ul; typedef unsigned long long ull; #define pi acos(-1.0) #define e exp(1.0) #define pb push_back #define mk make_pair #define fir first #define sec second #define scf scanf #define prf printf #define sqt sqrt(2.0) typedef pair<ll,ll> pa; const ll INF=0x3f3f3f3f3f3f3f3f; const int MAX_N=55; int N; int a[MAX_N],l[MAX_N],r[MAX_N]; int abs(int n){ return n>0?n:-n; } int main() { // freopen(".../.txt","w",stdout); // freopen(".../.txt","r",stdin); ios::sync_with_stdio(false); while(cin>>N&&N){ int i,j,k,L,R; for(i=1;i<=N;i++) cin>>a[i]; for(i=1;i<=N;i++){ L=0; for(j=1;j<i;j++){ L=max(L,r[j]-abs(a[i]-a[j])); } l[i]=L; r[i]=L+2*a[i]; } for(i=1;i<=N;i++){ L=l[i]; R=r[i]; for(j=1;j<=N;j++){ if(i==j) continue; if(j<i)//左边的正方形能覆盖的最大坐标 L=max(L,r[j]); else//右边的正方形能覆盖的最小坐标 R=min(R,l[j]); } if(L<R) cout<<i<<' '; } cout<<endl; } return 0; }