1879번 - 부끄러운 다각형

2차원 평면에 두 개의 다각형이 있다. 우리는 이 두 개의 다각형 중 하나를 x축 방향으로 이동시킬 수 있다. x축 외의 방향으로는 이동시킬 수 없으며, 이동하는 중에는 서로 두 다각형이 겹칠 수도 있다.

우리는 두 개의 다각형을 가능하면 빡빡하게 배치해야 한다. 즉 두 개의 다각형 위에 있는 모든 점들 중 x좌표의 최댓값과 최솟값의 차이를 최소로 해야 하는 것이다.

하지만 하나의 조건이 있다 : 두 개의 다각형이 지나치게 가까워지면, 서로 굉장히 부끄러워하는 성질이 있다. 따라서, 이들이 서로 부끄러워하지 않을 정도의 거리인 L만큼은 떨어져 있어야 한다. 즉, 두 다각형에서 임의의 점을 각각 하나씩 잡았을 때, 어떤 경우에도 두 점 사이의 거리가 L보다 작아서는 안 된다는 것이다.

예를 들어 두 개의 다각형이 위와 같이 위치하고 있다고 하자. 만일 L=10.0이라면, 두 다각형을 옆의 그림과 같이 배치하여 두 개의 다각형 위에 있는 모든 점들 중 x좌표의 최댓값과 최솟값의 차이를 최소인 100으로 만들어 줄 수 있다. 이 값이 100보다 클 수는 없다. - 이미 하나의 다각형에서만 구해도 100을 이루기 때문이다.

L값과 두 개의 부끄러운 다각형이 주어지면, 거리가 L만큼은 떨어져 있으면서도 가능하면 빽빽하게 배치했을 때, 두 개의 다각형 위에 있는 모든 점들 중 x좌표의 최댓값과 최솟값의 차이를 최소로 하는 프로그램을 작성하시오.

첫째 줄에는 실수 L(0.1≤N≤50.0)이 주어진다. 둘째 줄에는 첫 번째 다각형의 꼭짓점의 개수 N1이 주어진다. 이어서 N1개의 줄에 걸쳐 다각형을 이루는 꼭짓점의 x좌표와 y좌표가 빈 칸을 사이에 두고 반시계 방향으로 주어진다. 이어서 두 번째 다각형의 꼭짓점의 개수 N2가 주어지고 이어서 N2개의 줄에 걸쳐 다각형을 이루는 꼭짓점의 좌표가 마찬가지 형태로 주어진다.
  다각형의 꼭짓점의 개수는 2 이상 15 이하이다. (2인 경우 선분을 이루게 된다) 입력되는 모든 좌표는 음 아닌 정수로 500을 넘지 않는다. 다각형은 단순 다각형으로 서로 교차하거나 닿아 있지 않다.

첫째 줄에 두 다각형의 거리가 L만큼은 떨어져 있으면서도 가능하면 빽빽하게 배치했을 때, 두 개의 다각형 위에 있는 모든 점들 중 x좌표의 최댓값과 최솟값의 차이의 최솟값을 출력한다. 소수점 셋째 자리에서 반올림하여 출력하며, 소수점 이하 자리가 0이여도 반드시 출력해야 한다.