728x90
https://www.acmicpc.net/problem/9061
9061번: 두 직사각형
입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 첫 줄에 자연수 N (1 ≤ N ≤ 10000) 이 주어지며, 그 이후 N
www.acmicpc.net
사용 알고리즘
세그먼트 트리 (초반에 생각을 못해서 세그먼트 트리를 이용했다.)
정렬
풀이
그냥 x좌표나 y좌표 중 하나로 잡고 정렬해서 모든 점에 대해서 그 점을 기준으로 두 직사각형을 만들어서 답을 구하면 된다. 이때 두 직사각형은 모든 점을 다 포함해야 함으로 왼쪽과 오른쪽에 있는 모든 점들의 y좌표의 최대값과 최소값을 알아야 한다. 이를 구하기 위해 세그먼트 트리를 이용하면 된다. (물론 사용하지 않아도 된다.)
시간 복잡도는 O(N log(N))이다. (참고로 log는 이진로그이다.)
(추가)
왼쪽에서 오른쪽으로 갈 때의 최소와 최대, 오른쪽에서 왼쪽으로 갈 때의 최소와 최대를 미리 구해놓고 계산하면 더 쉽게 해결 할 수 있다.
코드
더보기
세
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
//세그트리
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
struct data{
int x,y;
}A[10003];
inline bool cmp(data a,data b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
ll M[40003],m[40003],Lt,Lb,Rt,Rb,res;
int S,E,N,i,st;
ll MAX(int s,int e,int pos){
if(S>e||s>E)return -9e18;
if(S<=s&&e<=E)return M[pos];
return max(MAX(s,(s+e)/2,pos*2),MAX((s+e)/2+1,e,pos*2+1));
}
ll MIN(int s,int e,int pos){
if(S>e||s>E)return 9e18;
if(S<=s&&e<=E)return m[pos];
return min(MIN(s,(s+e)/2,pos*2),MIN((s+e)/2+1,e,pos*2+1));
}
void f(){
if(N<=2){
res=0;
return;
}
int p;
sort(A+1,A+1+N,cmp);
memset(M,-9e18,sizeof(M));
memset(m,9e18,sizeof(m));
for(i=1;i<=N;i++){
p=(i+st-1)/2;M[i+st-1]=m[i+st-1]=A[i].y;
while(p){
M[p]=max(M[p*2],M[p*2+1]);
m[p]=min(m[p*2],m[p*2+1]);
p/=2;
}
}
for(i=1;i<=N;i++){
S=1,E=i;
Lt=MAX(1,st,1);
Lb=MIN(1,st,1);
S=i+1,E=N;
Rt=MAX(1,st,1);
Rb=MIN(1,st,1);
res=min(res,max((A[i].x-A[1].x)*(Lt-Lb),(A[N].x-A[i+1].x)*(Rt-Rb)));
}
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&N);st=1;
while(st<N)st*=2;
for(i=1;i<=N;i++)scanf("%lld%lld",&A[i].x,&A[i].y);
res=9e18;
f();
for(i=1;i<=N;i++)swap(A[i].x,A[i].y);
f();
printf("%lld\n",res);
}
return 0;
}
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
//(추가)
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const ll R=10003;
struct co{ll x,y;}A[R];
bool cmp(co a,co b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
int T,N,i,j;
ll ans,Lm[R],LM[R],Rm[R],RM[R];
void f(){
if(N<=2){ans=0;return;}
sort(A+1,A+N+1,cmp);
Lm[1]=LM[1]=A[1].y;
for(i=2;i<=N;i++){Lm[i]=min(Lm[i-1],A[i].y);LM[i]=max(LM[i-1],A[i].y);}
Rm[N]=RM[N]=A[N].y;
for(i=N-1;i>=1;i--){Rm[i]=min(Rm[i+1],A[i].y);RM[i]=max(RM[i+1],A[i].y);}
for(i=1;i<N;i++)ans=min(ans,max((A[i].x-A[1].x)*(LM[i]-Lm[i]),(A[N].x-A[i+1].x)*(RM[i+1]-Rm[i+1])));
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(i=1;i<=N;i++)scanf("%lld%lld",&A[i].x,&A[i].y);
ans=9e18;
f();
for(i=1;i<=N;i++)swap(A[i].x,A[i].y);
f();
printf("%lld\n",ans);
}
return 0;
}
|
cs |
ㅇ
728x90
'BAEKJOON > Nationwide Internet Competition' 카테고리의 다른 글
| BAEKJOON 9008번: Castle (0) | 2022.02.15 |
|---|---|
| BAEKJOON 9027번: Stadium (0) | 2022.01.19 |