Taula Cremada
Bambino ha tallat amb el seu ex. Ara fa tot el ritual de desprendre’s de totes les coses de l’ex, incloent les seves possessions. Però no tot és tan fàcil. L’ex fumava i la taula del menjador de Bambino està plena de cremades, i tampoc anem a llençar la taula per això. No obstant té 3 tires de cinta amb les que pot fer un triangle. Pot Bambino formar un triangle que tapi totes les cremades?
Entrada
El problema té diversos casos. Per a cada cas el problema comença amb un nombre n que indica les cremades., entre 1 i 10. Per cada cremada hi haurà una linea amb dos nombres, les seves coordenades x i y. S’assumeix que 0,0 és el centre de la taula, que és infinita. x i y estaran entre 0 i 10.
Sortida
Si es pot cobrir la taula amb les tres cintes formant un triangle, la resposta és "SI". Si no hi ha cap combinació possible, la resposta és "NO"
Exemple d'Entrada
4
0 0
0 2
2 0
2 2
5
0 0
0 2
2 0
2 2
1 1
0Exemple de Sortida
SI
NODemostració del primer cas
Comments
.
This comment is hidden due to too much negative feedback. Click here to view it.
No sé si acabo d'entendre el problema.
(Sembla que la descripció de la sortida està copiada i enganxada de la de l'entrada? Entenc que hem de respondre si és possible cobrir les cremades o no.)
De la manera que està explicat jo ho he entès de la següent manera: del conjunt de punts donat cal trobar un triplet de subconjunts disjunts on tots els punts de cada un siguin col·lineals entre ells. El fet de si formen un triangle o no és irrellevant: qualsevol conjunt de tres línies no paral·leles formarà un triangle a l'espai euclidià.
Tanmateix, això faria que el segon cas d'exemple estigués malament. Exemple arbitrari de com tapar totes les cremades amb tres cintes:
Cal que tots els punts es trobin dins (o sobre la frontera) del triangle format? Tot i que no s'especifica a l'enunciat, sembla ser una assumpció raonable tenint en compte els casos d'exemple proporcionats.
Hola! Els punts han d'estar en el mateix triangle. Això inclou els seus vèrtexs
Gràcies per l'aclariment :)
chucha
Que carajo es esto???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? XD
Un triangulo