首页 > 代码库 > POJ 3347 Kadj Squares (线段覆盖)
POJ 3347 Kadj Squares (线段覆盖)
题目大意:给你几个正方形的边长,正方一个顶点在x轴上然后边与x轴的夹角为45度,每个正方形都是紧贴的,问从上面看能看的正方形的编号
题目思路:线段覆盖,边长乘上2防止产生小数,求出每个正方形与x轴平行的对角线的起始x坐标,剩下的就是线段了。
#include<cstdio> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> #define INF 0x3f3f3f3f #define MAX 100005 using namespace std; struct node { int sx,y,ex,dist; } point[MAX]; int vis[MAX],n; void Find(int sx,int ex,int pos) { for(int i=0; i<n; i++) { if(i==pos || (point[pos].y >= point[i].y)) continue; if((sx>=point[i].sx && ex<=point[i].ex) || sx>=ex) { vis[pos]=1; return; } else if(sx<=point[i].ex && sx>=point[i].sx) { sx=point[i].ex; } else if(ex<=point[i].ex && ex>=point[i].sx) { ex=point[i].sx; } } } int main() { int d,sx,ex; int op; while(scanf("%d",&n),n) { op=0; memset(vis,0,sizeof(vis)); for(int i=0; i<n; i++) { scanf("%d",&d); point[i].dist=d; point[i].y=d; point[i].sx=0; for(int j=0; j<i; j++) { point[i].sx=max(point[i].sx,point[j].ex-abs(point[i].dist-point[j].dist)); } point[i].ex=point[i].sx+2*d; } for(int i=0; i<n; i++) { ex=point[i].ex; sx=point[i].sx; Find(sx,ex,i); } for(int i=0; i<n; i++) { if(!vis[i]) { if(!op) { op=1; printf("%d",i+1); } else printf(" %d",i+1); } } printf("\n"); } return 0; }
POJ 3347 Kadj Squares (线段覆盖)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。