2008 witnessed the magnificent opening ceremony of the 29th Beijing Olympic Games. The gorgeous fireworks shows during the ceremony have left deep impressions on millions of people all over the world.
Fireworks are always used to accompany many festivities. Today, in important events and festivities, fireworks are still guaranteed sights.
Recently, a new advanced device for generating fireworks is put into use. This device can precisely control the shapes and the positions and the colors of fireworks easily and arbitrarily. To use this device, we just need to set up its range of targets, as well as the appearances of fireworks. However, this kind of devices have a fatal flaw - if two or more devices have common part(s) in their ranges of targets, even just a point, it may cause some unpredictable errors, and finally result in unexpected appearances.
Now here comes your task: given the target ranges of two devices, please determine whether they have common part(s).
Note that the target range of a device will always be a none hole and none self-intersecting polygon on a plane, and the edges are considered as a part of the range. To simplify the problem, it’s guaranteed that interior angles of polygon will never be straight angles.