https://www.acmicpc.net/problem/17619
17619번: 개구리 점프
첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 좌표는 0이상 109이하이다. 통나무들은 주어진 순서대로 1번부터 번호가 붙어 있다. 서로 다른 두 통나무는 (끝점에서도) 만나지 않는다. 다음 Q개의 줄에 서로 다른 두 통나무의 번호가 주어진다. (1 ≤ N ≤ 100,00
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
typedef struct wood
{
int x1, x2, y;
int num;
}wd;
bool cmp(wd a, wd b)
{
return a.x1 < b.x1;
}
int main(void)
{
int n,q;
int qus_1, qus_2;
int now_group = 1;
int group[100] = {0,};
int max_x2=0;
scanf("%d %d", &n, &q);
vector<wd> v;
wd temp;
for(int i=1; i<=n; i++) //입력.
{
temp.num = i;
scanf("%d %d %d", &temp.x1, &temp.x2, &temp.y);
v.push_back(temp);
}
sort(v.begin(), v.end(), cmp); //x1의 순서로 정렬.
for(int i=0; i<n; i++)
{
group[v[i].num] = now_group;
max_x2=v[i].x2;
if(i==n-1)
{
break;
}
for(int j = i+1; max_x2>=v[j].x1; j++)
{
printf("=1.1= %d : %d\n", max_x2, v[j].x1);
if(v[j].x2 > max_x2)
{
max_x2 = v[j].x2;
}
group[v[j].num] = now_group;
i++;
printf("=1.2= %d : %d\n", max_x2, v[j].x1);
}
now_group++;
}
for(int i = 0; i<=n; i++)
{
printf("=2=%d : %d\n", i, group[i]);
}
for(int i=0; i<q; i++)
{
scanf("%d %d", &qus_1, &qus_2);
if(group[qus_1] == group[qus_2]) //같은 그룹이면 연결되어있다.
{
printf("1\n");
}
else
{
printf("0\n");
}
}
return 0;
}
'정보올림피아드-KOI > 기출문제' 카테고리의 다른 글
| "이것이 취업을 위한 코딩 테스트다 with 파이썬" (0) | 2020.08.09 |
|---|---|
| 2019년 정보올림피아드 2차 초등 2번 (0) | 2020.01.18 |
| 2019년 정보올림피아드 2차 초등 1번 (0) | 2020.01.18 |
| 정올 기출 풀이를 시작하며.... (0) | 2019.12.17 |
