5419 북서풍 - 백준

북서풍 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

6705

2274

1448

33.816%

문제

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다.

작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 xi, yi가 주어진다. 두 섬의 좌표가 같은 경우는 없다. (-109 ≤ xi, yi ≤ 109)

출력

각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.

예제 입력 1 복사

2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1

예제 출력 1 복사

5
3

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2005 E번

• 문제를 번역한 사람: baekjoon

 

풀이

북서풍이 분다 -> 동쪽과 남쪽 사이로 바람이 분다.(우측, 하측 바람)

작은섬이 여러개 (좌표로 표현, y좌표 증가는 북쪽, x좌표 증가 동쪽)

 

북서풍을 타고 향해할 수 있는 섬의 쌍의 수를 구하는 프로그램 작성

 

입력

첫째 줄 테스트 케이스 갯수

tc 첫째줄

n: 섬의 수

n개의 줄

섬의 좌표 x, y <- 같은 좌표는 없음

 

북서풍을 타고 향해할 수 있는 섬의 쌍의 갯수 출력 필요

 

tc 분석

 

-10, 10                                                             10, 10

 

 

-10 -10                                                             10, -10

 

-10, 10에서 start시

1. -10, -10 가는거 

2. 10, 10 가는거

3. 10, -10 가는거

 

-10, -10에서 start시

1. 10, -10 가는거

 

10, 10에서 start시

1. 10, -10 가는거

 

총 5개

 

 

1, 3 

            2,2

                      3,1

 

1, 3 start시

1. 2,2 가는거

2. 3, 1가는거

 

2,2 start시

1. 3,1 가는거

 

총 3개

 

섬을 전체 순회하면서 가능한 쌍의 갯수를 찾아본다.

 

N 갯수가 75000 이므로 N2만 아니면 통과 가능할 것으로 보인다.

예전에 이거 하나 압축해서 하는 것이 좋다고 본 것 같다.

Y값으ㅣ  -10^9 ~ 10^9로 엄청 크기에 이거 크기를 줄여본다.

 

그리고 한 방향으로 체크하는 쿼리 형태로 해야 하는 것이면 세그먼트 트리가 더 유리할 것으로 보인다.

현재 내 위치에서 북쪽 서쪽에 있는 섬의 갯수를 알고 싶은것을 query

그리고 현재 자기 위치도 표현하는 update구문

 

아이디어

1. 일단 좌표를 받아서 저장

2. x축 오름차순, y축 내림차순 저장 (사유: 북서풍), 이 때 y축 값을 비교해서 1 부터 N 까지 증가시켜서 저장 시켜본다.(이러면 마이너스로 가던게 뒤집어져서 양수로 저장이된다. 우상향)

-10, 10                                                             10, 10

 

 

-10 -10                                                             10, -10

 

이게

 

-10, 2                                                             10, 2

 

 

-10 1                                                            10, 1

이렇게 된다.

 

저장이 그러면

 

-10,1 -10,2 10,1 10,2 순으로 저장될 것으로 보인다.

3. 이를 정렬된 순서대로 세그먼트 트리에 저장

-10, 1 추가 하면

 

 구간은 번호 좌표

                                 1-4

                                    1

 

               1-2                                          3-4

                 1                                             0

 

1번 좌표                 

10, 2                ()                     ()                         ()

1                      0                     0                          0

 

 

                                 1-4

                                    2

 

               1-2                                          3-4

                 2                                             0

 

1번 좌표      2번 좌표       

(-10, 1 )       (-10, 2)                     ()                         ()

1                      1                          0                          0

 

 

 

                                 1-4

                                   3

 

               1-2                                          3-4

                 3                                             0

 

1번 좌표      2번 좌표       

(-10, 1 )       (-10, 2)                     ()                         ()

3번 좌표

(-10, 1)

2                      1                          0                          0

 

 

 

                                 1-4

                                   4

 

               1-2                                          3-4

                 4                                             0

 

1번 좌표      2번 좌표       

(-10, 1 )       (-10, 2)                     ()                         ()

3번 좌표     4번 좌표

(10, 1)        (10,2)

2                      2                          0                          0

 

 

 

 

 

 

 

2번째 tc

                                 1-4

                                    1

 

               1-2                                          3-4

                 1                                             0

 

1번 좌표                 

1, 1                ()                     ()                         ()

1                      0                     0                          0

 

 

                                 1-4

                                    2

 

               1-2                                          3-4

                 2                                             0

 

1번 좌표      2번 좌표       

(1, 1 )            (2, 2)                     ()                         ()

1                      1                          0                          0

 

 

 

                                 1-4

                                   3

 

               1-2                                          3-4

                 2                                             1

 

1번 좌표      2번 좌표          3번 좌표

(1, 1 )            (2, 2)                     (3,3)                      ()

1                      1                          1                          0

 

 

코드

package test5419;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
	static class Matrix {
		int x;
		int y;

		public Matrix(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static int N;
	static int TC;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);
		TC = sc.nextInt();

		for (int test_case = 0; test_case < TC; test_case++) {
			N = sc.nextInt();

			List<Matrix> matrixList = new ArrayList<>();

			for (int i = 0; i < N; i++) {
				matrixList.add(new Matrix(sc.nextInt(), sc.nextInt()));
			}

			// y기준 내림차순
			Collections.sort(matrixList, (a, b) -> b.y - a.y);
			// counter의 값을 지정한다.
			int yCounter = 1;
			int[] yIndexTmp = new int[N];
			for (int i = 0; i < N; i++) {
				// y값이 이전 값보다 1이라도 커지면 y counter 값을 키운다. 그래야 압축이 됨.
				if (i > 0 && matrixList.get(i).y != matrixList.get(i - 1).y) {
					yCounter++;
				}
				yIndexTmp[i] = yCounter;
			}
			for (int i = 0; i < N; i++) {
				// y값이 이전 값보다 1이라도 커지면 y counter 값을 키운다. 그래야 압축이 됨.
				matrixList.get(i).y = yIndexTmp[i];
			}

			// x가 같은 경우 y 기준 오름 차순
			// 아닌 경우 x 기준 오름 차순
			// 이유: y 축변환해서 위아래가 뒤집힘
			Collections.sort(matrixList, (a, b) -> {
				if (a.x == b.x) {
					return a.y - b.y;
				} else {
					return a.x - b.x;
				}
			});

			SegmentTree segTree = new SegmentTree();

			long res = 0;
			for (int i = 0; i < N; i++) {
				// top down query
				res += segTree.query(1, N, 1, 1, matrixList.get(i).y);
				// top down update
				segTree.update(1, N, 1, matrixList.get(i).y);
			}
			sc.write(res + "\n");
			
		}

		sc.close();

	}

	static class SegmentTree {
		long segTree[];

		SegmentTree() {
			segTree = new long[4 * N];
		}

		long query(int start, int end, int node, int left, int right) {
			// left의 값이 end를 넘어가거나 start 값이 right보다 커지면 0으로 초기화
			if (end < left || right < start) {
				return 0;
			}
			// start가 left 보다 크고 end가 right보다 작으면 현재 seg tree 출력
			if (left <= start && end <= right) {
				return segTree[node];
			}
			int mid = (start + end) / 2;
			return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);
		}

		void update(int start, int end, int node, int index) {
			// index 값이 start 보다 작고 end 보다 크면 update 못함
			if (index < start || end < index) {
				return;
			}
			// segTree의 현재 node 값을 1 update 한다.
			segTree[node] += 1;
			// start랑 end랑 같으면 update stop
			if (start == end) {
				return;
			}
			int mid = (start + end) / 2;
			update(start, mid, node * 2, index);
			update(mid + 1, end, node * 2 + 1, index);
		}
	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}