가로 세로 선 3개만 그어서 모든 점을 덮을 수 있는가?

5884번: 감시 카메라 n개의 점이 있는데 수직선이나 수평선으로 3개만 그어서 모든 점을 덮을 수 있는지 체크하는 문제 점의 좌표 범위가 10^9이다 보니 하나하나 다 그어보면 당연히 시간초과 날것이고 X좌표를 기준으로 그룹을 묶고, Y좌표를 기준으로 그룹을 묶는다 그러면 어떤 X = x좌표를 기준으로 수직선을 그어보면, 해당하는 y좌표들을 알 수 있다 그러면 그러한 y좌표가 여러개 있다면?  Y = y로 수평선을 또 그어야할 것이다   근데 해당하는 Y = y2가 하나만 존재한다면 Y = y2로 수평선을 그을 필요가 없다   그러므로 모든 X = x에 대해 순회해봐서 x에 대응하는 y들을 다시 하나씩 순회해본 다음 해당하는 y좌표값들 개수가 2개 이상인 경우가 존재하면 그 쪽으로 수평선을 그어야하므로..

  • format_list_bulleted 브루트포스
  • · 2024. 11. 18.
  • textsms

수천개의 점들 중에서 가장 넓이가 큰 정사각형을 찾는 방법

9015번: 정사각형 점이 n개  그냥 한다면 O(N^4)이겠지만 당연히 안될거고 O(N^3)인 방법도 있긴한데 N  정사각형 성질을 이용하면.. 임의의 두 점 A(x1,y1), B(x2,y2)을 먼저 잡고 벡터 AB를 구한다 벡터 AB = OB - OA = (x2-x1, y2-y1)으로 구할 수 있다   다음 벡터 AB를 시계방향으로 90도 회전하면 벡터 AD를 구할 수 있다 90도 회전하는 방법은? (x,y) >> (-y,x)로 되므로 벡터 AD = (-y2+y1, x2-x1)이 된다 https://deepdata.tistory.com/1388 벡터 (x,y)를 90도 회전하는 방법1. 회전 행렬 벡터 (x,y)는 극좌표계를 이용하면 (rcosθ,rsinθ)   이 상황에..

  • format_list_bulleted 브루트포스
  • · 2024. 11. 17.
  • textsms
벡터 (x,y)를 90도 회전하는 방법

벡터 (x,y)를 90도 회전하는 방법

1. 회전 행렬 벡터 (x,y)는 극좌표계를 이용하면 (rcosθ,rsinθ)   이 상황에서 A만큼 회전시킨다면... Q의 좌표는 (rcos(θ+A),rsin(θ+A))   삼각함수의 덧셈정리를 이용하면 cos(θ+A)=cosθ∗cosA−sinA∗sinθ이고  sin(θ+A)=sinθ∗cosA+cosθ∗sinA x=rcosθ,y=rsinθ이므로 이를 대입하면... $x' = rcos (\theta + A) = x cos A - y sin A, y' = rsin (\theta + A) = ycosA..

  • format_list_bulleted 기하학
  • · 2024. 11. 16.
  • textsms
숨어있는 기준을 찾는 브루트포스1 - 수많은 좌표들을 얼마나 평행이동해야 일치하는가

숨어있는 기준을 찾는 브루트포스1 - 수많은 좌표들을 얼마나 평행이동해야 일치하는가

5588번: 별자리 찾기 좌표 집합 A와 B가 주어질때 A를 얼마나 평행이동 시켜야 B의 부분집합이 될 수 있는가? 아래의 경우 2,-3 이동시키면 B의 빨간 부분과 일치시킬 수 있다   A의 별 개수 m이 최대 200개이고 B의 별 개수 n이 최대 1000개 x,y값은 최대 10^6까지...  그러면 200개 * 1000개 돌아보면서... 평행이동 시킬 수 있는 양 10^6까지 하나하나 돌아봐야하나?? 그런데 A의 모든 점은 서로 동일하게 (dx,dy)만큼 이동한다는 점 +  B의 점들 집합의 일부가 되어야하므로, A의 한 점이 B의 모든 점 각각에 대하여 얼마만큼 이동해야 가능한지  (dx,dy)를 모두 구해놓는다면?    가능한 (dx,dy) 후보는 최대 1000개이고 각각에 대해서 A의 모든 점에..

  • format_list_bulleted 브루트포스
  • · 2024. 11. 9.
  • textsms

주어진 점들 중 최대 맨해튼 거리(Manhattan Distance)를 빠르게 찾는 방법

https://atcoder.jp/contests/abc178/tasks/abc178_e E - Dist MaxAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp   n개의 점이 주어질때, 이들 쌍으로 만들 수 있는 가장 긴 맨해튼 거리는? n이 최대 20만이기 때문에 O(N2)으로 직접 비교할 수는 없다 두 점 (xi,yi), (xj,yj)에 대하여 맨해튼 거리는 |xi - xj| + |yi - yj| = A A는 xi,xj, yi,yj 사이 대소관계에 따라 다음과 같이 풀어낼 수 있다 1) $x_{i} >= x_{j}..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 10. 23.
  • textsms
평면 위 두 직사각형이 서로 겹치는 직사각형의 좌표 구하는 놀라운 방법

평면 위 두 직사각형이 서로 겹치는 직사각형의 좌표 구하는 놀라운 방법

두 직사각형의 왼쪽 하단 좌표, 오른쪽 상단 좌표 (x1,y1), (x2,y2), (x3,y3), (x4,y4)가 각각 주어질때, 이 두 직사각형이 서로 겹쳐서 생기는 영역의 좌표를 구해본다면?   E의 좌표가 (x5,y5), F의 좌표가 (x6,y6)라고 한다면... 놀랍게도 이를 구하는 공식이 있다 x5 = max(x1,x3)y5 = max(y1,y3) x6 = min(x2,x4)y6 = min(y2,y4) 만약 x5 > x6이거나 y5 > y6이면 두 직사각형이 겹치지 않는다 근데 몇개 해보니까 진짜 맞는듯? 왼쪽 하단은 max, 오른쪽 상단은 min     조건 하나하나 생각해서 할려고 하면 거의 무조건 틀리더라 그냥 공식 써버리는게 제일 편함 #직사각형1 (x1,y1), (x2,y2)#직사각형2..

  • format_list_bulleted 기하학
  • · 2024. 8. 29.
  • textsms