Home | I n t e r n e t C o n t e s t | i n t e r n e t c o n t e s t |
C E O I 2 0 0 0 |
Regulations Schedule Organising Team Cluj&Romania Sponsors Secretariat Internet Contest Links
|
Day one problems are available here. Day 2 [ Problem 4 | Problem 5 | Problem 6 ] Problem 6 : Enlightened landscape Consider a landscape composed of connected line segments: Above the landscape, N light bulbs are hang at the same height T in various horizontal positions. The purpose of these light bulbs is to light up the entire landscape. A landscape point is considered lit if it can "see" a light bulb directly, that is, if the line segment which links the point with a bulb does not contain any other landscape segments point. Task Write a program that determines the mi-ni-mum number of light bulbs that must be switched on in order to illuminate the entire landscape. Input Input file name: LIGHT.IN Line 1: M Lines 2..M+1: Xi Hi Line M+2: N T Line M+3: B1 B2 ... BN Output File name: LIGHT.OUT Line 1: K Line 2: L1 L2 ... LK Limits Example LIGHT.IN LIGHT.OUT 6 2 1 1 1 4 3 3 4 1 7 1 8 3 11 1 4 5 1 5 6 10 |
||