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);
- while(!q.empty()){
- int tmp = q.front(); q.pop();
- if(!IsVisited[tmp]){
- if(tmp == Table.size()-1){
- return true;
- }
- q.push(tmp);
- IsVisited[tmp] = true;
- }
- }
- return false;
- }
- 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);
- int r = 10;
- for(int i = 0; i < N; i++){
- int x1 = Verticles[i].first;
- int y1 = Verticles[i].second;
- for(int j = i+1; j < N; i++){
- int x2 = Verticles[j].first;
- int y2 = Verticles[j].second;
- if((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) < r * r){
- g.AddEdge(i,j);
- }
- }
- if(x1-XL < r){
- g.AddEdge(i,N);
- }
- if(x1-XR < r){
- g.AddEdge(i, N+1);
- }
- }
- if(g.Path()){
- cout << "Yeas";
- }
- else
- {
- cout << "Nope";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement