All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Government is surveilling the entire planet in search of black money, and now there are N satellites orbiting Earth. Each satellite has sensors to detect black money transaction on the visible half of the planet. For example, when a satellite is passing over north pole, it's sensors can detect any transaction in the northern hemisphere. This surveillance has become a real pain point for some businessmen, as the satellite sensors are really good. A powerful businessman wants to conduct a big black money transaction somewhere on the planet surface. To do this, he must first sabotage all satellites which would be able to detect the transaction. The businessman can choose any place and time for the transaction, as long as it is on the planet surface. Please help him by finding the minimum number of satellites that must be sabotaged so that the transaction goes undetected. He has promised you a small fraction of the money (in old currency) as a reward for your services.
<object data="https://s3.amazonaws.com/codechef_shared/download/upload/FEB17/SC.svg" type="image/svg+xml" height="350"> </object> <object data="https://s3.amazonaws.com/codechef_shared/download/upload/FEB17/T2.svg" type="image/svg+xml" height="350"> </object>
The ith satellite orbits along longitude li, and at time t=0, is in phase pi. Phase of an orbiting body is the angle between north pole, planet center and the orbiting body. If phase pi is less than 180 degree, the body lies on longitude li somewhere between north pole and south pole. If phase is more than 180 degree, the body lies on longitude li-180 somewhere between south pole and north pole.
Extra Explanation: Note that the formulation of longitude and phase is slightly different from the system of longitudes and latitudes we use to denote points on earth's surface. It is closer to Spherical coordinate system, but we have constrained the azimuth angle (li in the figure above) to be between 0 and 180, so the azimuth angle of an orbiting satellite does not change, and polar angle can be anywhere between 0 and 360. At time t, the ith satellite is located at x = sin(pi + t) * cos(li), y = sin(pi + t) * sin(li), z = cos(pi + t).
Assumptions to be made:
- The transaction takes place on a place which has arbitrarily small(but non zero) area.
- The transaction lasts for arbitrarily short(but non zero) duration.
- All satellites have circular orbit which is very far away from the planet’s surface.
- All satellites orbit at the same distance and the same speed.
- All angles are in degrees.
- The geometric center of the Planet is same as its center of mass.
- No special or general relativistic effects.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of satellites. The next N lines contain two space separated integers each, pi and li.
For each test case, output a single line containing the minimum number of satellites that must be sabotaged to conduct a successful transaction.
- 1 ≤ T ≤ 10
- 3 ≤ N ≤ 50
- 0 ≤ li ≤ 179
- 0 ≤ pi ≤ 359
- All li are distinct.
- All pi are distinct modulo 180.
Input: 2 3 10 90 310 30 305 150 3 10 90 230 30 125 35 Output: 0 0
- Sub task #1: N = 3 (10 points)
- Sub task #2: N ≤ 20 (30 points)
- Sub task #3: N ≤ 50 (60 points)
Example case 1: The businessman can do transaction at time t=0, at longitude 90, and phi 230 (90W, 40S), where no orbiting satellite can see them, so he does not need to sabotage any of them.
Example case 2: The businessman can do transaction at time t=160 (after all satellites have complete 160 degrees of rotation), at longitude 125, and phi 267 (55W, 3S). No satellite has to be sabotaged in this case either.
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.