Universal Socket
InterviewTime limit2sMemory limit256 MB
Given n labeled points (phase or neutral), decide whether two points of opposite labels sit exactly distance d apart.
- Level
Easy3 of 10
- Topics
- Geometry, Hash map, Brute force, Implementation
- Solved
- No attempts yet
Problem
An electrical socket is built as follows. It has two contacts, and a wire runs to each contact. These contacts, along with the wires attached to them, are called "phase" and "neutral". The outer panel of the socket has two holes, which are used to connect electrical appliances to it.
Electrical appliances connect to a socket using so-called plugs. A plug has two contacts, which are inserted into the holes of the socket. When the plug is inserted into the socket, the corresponding contacts of the plug and the socket touch and close the circuit.
Different countries use plugs with different distances between contacts, which causes serious problems for travelers. A large company decided to release a unique product: a socket into which a plug from almost any country can be inserted. This socket has n holes. Some of them are connected to neutral, and the rest are connected to phase.
Your task is to determine whether a plug with distance d between its contacts can be connected to this socket so that one contact of the plug is closed to neutral and the other to phase.
Input
The first line contains two integers n and d (1 ≤ n ≤ 200, 1 ≤ d ≤ 10000).
Introduce a rectangular Cartesian coordinate system on the outer panel of the socket. The next n lines contain three integers each: xi, yi, ti (−10000 ≤ xi, yi ≤ 10000; 0 ≤ ti ≤ 1). This means that there is a hole at the point with coordinates (xi, yi). If ti = 1, the contact corresponding to this hole is connected to phase. If ti = 0, the contact corresponding to this hole is connected to neutral.
All holes are at distinct points.
Output
Output Yes if this plug can be correctly connected to this socket, and No otherwise.