Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- class Graph {
- public:
- Graph(int n) {
- Table.resize(n);
- for (int i = 0; i < n; i++) {
- Table[i].resize(n);
- }
- }
- ~Graph() {}
- void AddEdge(int x, int y) {
- Table[x][y] = 1;
- Table[y][x] = 1;
- }
- bool Path() {
- vector<bool> IsVisited;
- IsVisited.resize(Table.size());
- queue<int> q;
- q.push(Table.size() - 2);
- IsVisited[Table.size()-2] = 1;
- while (!q.empty()) {
- int tmp = q.front();
- q.pop();
- for (int i = 0; i < Table.size(); i++) {
- if (Table[tmp][i] == 1) {
- if (!IsVisited[i]) {
- if (i == Table.size() - 1) {
- return false;
- }
- q.push(i);
- IsVisited[i] = true;
- }
- }
- }
- }
- return true;;
- }
- private:
- vector<vector<int>> Table;
- };
- int main() {
- int XL = 0; int XR = 0;
- cin >> XL; cin >> XR;
- int R = 0;
- cin >> R;
- int N = 0;
- cin >> N;
- vector<pair<int, int>> Verticles;
- for (int i = 0; i < N; i++) {
- int x = 0; int y = 0;
- cin >> x; cin >> y;
- pair<int, int> a;
- a.first = x;
- a.second = y;
- Verticles.push_back(a);
- }
- Graph g(N + 2);
- double r = 48.000;
- for (int i = 0; i < N; i++) {
- int x1 = Verticles[i].first;
- int y1 = Verticles[i].second;
- for (int j = i + 1; j < N;j++) {
- int x2 = Verticles[j].first;
- int y2 = Verticles[j].second;
- if (abs(x2 - x1)*abs(x2 - x1) + abs(y2 - y1)*abs(y2 - y1) < r * r + R*R) {
- g.AddEdge(i, j);
- }
- }
- if (x1 - XL < r+R) {
- g.AddEdge(i, N);
- }
- if (XR - x1 < r+R) {
- g.AddEdge(i, N + 1);
- }
- }
- if (g.Path()) {
- cout << "Yeas";
- }
- else
- {
- cout << "Nope";
- }
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement