Jigsaw of Shadows

시간 제한0.5초메모리 제한2048 MB

요약
빛의 각도와 각 사람의 위치와 키가 주어질 때, 겹치는 그림자를 합친 도로의 총 길이를 구한다.
난이도

보통10점 중 5점

유형
정렬, 구간, 수학
정답자
아직 제출이 없습니다

문제

They finally did it! The flat-earthers managed to teleport themselves to an idealized flat world where no one can make fun of them anymore.

In this world, there is a perfectly straight, infinite road that runs along the xx-axis. Instead of a sun, they have something more illuminating: a gigantic flashlight elevated above the road, positioned infinitely far away to the west (negative xx-axis). This flashlight beams light at a precise angle with respect to the ground, illuminating the entire road.

There are NN flatlanders standing proudly at distinct positions along the road. As the light strikes each of them, it casts a shadow extending eastward (toward the positive xx-axis).

Eager to show off their flat-world knowledge, the citizens want to calculate how much of the road is covered by their shadows. However, with shadows potentially overlapping, they need your help to figure it out. Given the positions of the flatlanders and their heights, can you calculate the total length of the road covered by their shadows?

입력

The first line contains two integers θθ (10≤θ≤8010 ≤ θ ≤ 80) and NN (1≤N≤1051 ≤ N ≤ 10^5 ), indicating respectively the angle of the light beams and the number of flatlanders on the road. The angle is measured in degrees, clockwise from the ground to the light beams.

Each of the next NN lines contains two integers XX (0≤X≤3⋅1050 ≤ X ≤ 3 \cdot 10^5 ) and HH (1≤H≤10001 ≤ H ≤ 1000), indicating that a flatlander of height HH is located at position XX along the road. It is guaranteed that no two flatlanders share the same location.

출력

Output a single line with the total length of the road covered by the shadows of all flatlanders. The output must have an absolute or relative error of at most 10−410^{-4}.

예제3

  1. 예제 1

    입력
    45 3
    50 150
    0 100
    100 200
    
    예상 출력
    300
    
  2. 예제 2

    입력
    60 3
    50 150
    0 100
    100 200
    
    예상 출력
    215.47
    
  3. 예제 3

    입력
    30 3
    50 150
    0 100
    100 200
    
    예상 출력
    446.41016