데이터 구조 단조 스 택 + 기 하 고 층 빌딩 [HDU 5033]
6335 단어 데이터 구조
제목 의 대의:
한 사람 이 마 천루 가 가득 한 도시 에 와 서 모든 빌딩 은 너비 가 없다.직각 좌 표를 만들어 모든 건축 의 높이 를 제시 하고 지금 은 사람 에 게 (x, 0) 에 서서 하늘의 범 위 를 볼 수 있다.(즉, 고 층 건물 에 막 히 지 않 는 다).답 은 시각 크기 만 제시 해 야 한다.그래도 한참 생각 하고 나 서 야 생각 이 났 다.한 사람 이 볼 수 있 는 왼쪽 경계 에 대해 우 리 는 다음 식 을 얻 을 수 있다.
kmaxxi=min((Hj−Hi)/(Xj−Xi)),j<=i k m a x x i = m i n ( ( H j − H i ) / ( X j − X i ) ) , j <= i
왼쪽 계 의 기울 임 률 을 구하 면 이 범위 의 시각 각 을 반 해 할 수 있다.최소 화 를 구 하려 면 단조 로 운 스 택 으로 경사 율 을 줄 이면 된다.우 계 는 같은 이치 로 얻 을 수 있다.
SPJ 가 있 는데 정밀도 가 뭐 가 나 빠 요?
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000100,inf=1e9;
const double pi=3.1415926535;
int t,n,cnt;
stack int ,double> > s;// , 。
struct node{
int x,h,bian;
double l,r;
}a[maxn];
bool cmp(node p,node q){
return p.xbool cmp2(node p,node q){
return p.biandouble getk(int x,int y){
double x1=a[x].x,x2=a[y].x,y1=a[x].h,y2=a[y].h;
return (y2-y1)/(x2-x1);
}
int main(){
int i,j,q;double k,a1,a2;
scanf("%d",&t);
for(j=1;j<=t;j++){
scanf("%d",&n);
printf("Case #%d
",j);
cnt=0;
for(i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].h);
a[i].bian=inf;//
}
cnt=n;
scanf("%d",&q);
for(i=1;i<=q;i++){
cnt++;
scanf("%d",&a[cnt].x);
a[cnt].bian=i;
a[cnt].h=0;
}
sort(a+1,a+cnt+1,cmp);// , 。
while(!s.empty())s.pop();
for(i=1;i<=cnt;i++){// ,
while(!s.empty()){
k=getk(s.top().first,i);
if(k>=s.top().second)s.pop();
else break;
}
if(s.empty()){
a[i].l=0;
s.push(make_pair(i,double(inf)));
}
else {
a[i].l=getk(s.top().first,i);
s.push(make_pair(i,a[i].l));
}
}
while(!s.empty())s.pop();
for(i=cnt;i>=1;i--){// ,
while(!s.empty()){
k=getk(s.top().first,i);
if(k<=s.top().second)s.pop();
else break;
}
if(s.empty()){
a[i].r=0;
s.push(make_pair(i,double(-inf)));
}
else {
a[i].r=getk(s.top().first,i);
s.push(make_pair(i,a[i].r));
}
}
sort(a+1,a+cnt+1,cmp2);
for(i=1;i<=q;i++){
a1=atan(abs(a[i].l));
a2=atan(abs(a[i].r));
printf("%.10lf
",(pi-a1-a2)/pi*180);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.