https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRboY6f84DFAUo
2차원 평면에서 주어진 직선들로 구분되는 무한한 공간의 개수를 구하는 문제
무한한 공간의 개수를 S라 할때
직선이 1개일때는 S = 2이고 그 뒤로는 직선 집합의 기울기에 따라 다르다.
임의의 N개의 직선이 기울기가 모두 같다면, S = N+1이다.
(너무 자명? 직선이 추가되도 무한한 공간 1개를 2개로 나누기 때문에..)
기울기가 모두 같지 않다면 S = 2N개라고 생각하였다.
수학을 잘 못해서 엄밀한 증명은 못하고 그냥 막 그어보면서 규칙을 찾았다.. 허허
직선의 인풋은 x1 y1 x2 y2로 들어오는데
같은 직선이 존재할 수 도 있다. 가장 쉽게 중복되는 직선을 제거하면서 직선을 표현하는 방법은 절편과 기울기로만 표현하는 것이다.
x1,y1,x2,y2를 받으면 기울기 a를 계산하고 y0 = y1-a*x1 으로 y절편을 구하였다.
만약 x1==x2 면 기울기는 inf로, y절편 대신 x절편을 반환하였다.
기울기만 저장하는 세트 slope_set과 (기울기, 절편) 을 저장하는 세트 line_set를 사용하여 모든 직선을 저장하였다.
이 방법으로 중복되는 직선을 제거하였다고 생각한다.
기울기set의 요소가 1개면 나눠지는 공간은 len(line_set)+1, 요소가 1보다 많다면 len(line_set)*2가 된다.
주어진 G보다 적다면 G가 되기 위해서 더 필요한 직선의 최소 개수를 계산한다.
모든 직선이 평행하였더라도 1개를 다르게 그으면 총 무한한 공간의 수는 2*직선개수가 되므로,
필요 직선의 개수 = ceil(G/2)로 하여 더 필요한 직선의 개수를 적었다만 결과는...
(오답 : 87개의 테스트케이스 중 77개가 맞았습니다.)
별로 복잡한 문제가 아니라서 반례가 없을 것 같은데 ㅜ 왜 틀릴 꼬... 중복되는 직선이 잘 지워지지 않는걸까?
import math
def slope_y0(line):
x1,y1,x2,y2 = line
if x2 != x1:
slope = (y2-y1)/(x2-x1)
y0 = y1-slope*x1
else:
slope = math.inf
y0 = x1
return slope, y0
T = int(input())
for t in range(1,1+T):
G, N = list(map(int,input().split()))
slope_set = set()
line_set = set()
for _ in range(N):
slope, y0 = slope_y0(list(map(int,input().split())))
slope_set.add(slope)
line_set.add((slope,y0))
if len(slope_set) == 1:
num_area = len(line_set)+1
else:
num_area = len(line_set)*2
if num_area >= G:
anw = 0
else:
anw=math.ceil(G/2)-len(line_set)
print(f'#{t}', anw)
SWEA는 검색해도 잘 나오지도 않고, 질의응답도 별로 활발하지 않아 막혔을 때 풀기가 너무 어려운 듯 하다.
문제들도 전체적으로 알고리즘이 어려운 것보다 테스트 케이스가 너무 커서 최적화에 고민해야 되는 문제가 많다.
O(N^2)으로는 쉬운 문제인데 N의 최대 개수가 100000 막 이러니 어렵다.
