37 | 2021-01-08 20:24:50 | mraron | 2015. szeptember | cpp11 | Elfogadva | 2ms | 2100 KiB |
#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
#define all(s) (s).begin(),(s).end()
#define pb push_back
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define INF std::numeric_limits<int>::max()
#define tmax(a,b,c) max((a),max((b),(c)))
#define tmin(a,b,c) min((a),min((b),(c)))
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define mp make_pair
#ifndef ONLINE_JUDGE
# define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
# define LOG(x) ((void)0)
#endif
int d1[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int d2[8][2]={{1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,1},{1,-1},{-1,-1}};
//---PROGRAM KEZDETE---
//Egy kör
struct Kor {
int i,x,y,r; //hanyadik volt a bemenetben, x,y koordináta r sugár
bool upper; //felső-e?
bool lower; //alsó-e?
};
//szomszédsági lista a gráfnak
vector<vector<int>> adj(500);
vector<Kor> t;//bemenetről kapott körök
//egy adott felső csúcsból alsót keresünk
bool searchforlower(int i, bool tt[])
{
if(t[i].lower) return true; //megtaláltuk
bool ans=false;
for(int j=0;j<adj[i].size();++j) //szomszédjai
{
if(!tt[adj[i][j]]) //ebben a szomszédban még nem jártunk!
{
tt[adj[i][j]]=true; //ne menjünk ide újra...
ans|=searchforlower(adj[i][j], tt); //rekurzió ebbe a szomszédosba
}
}
return ans;
}
int main()
{
IO;
int n,m,k;cin>>n>>m>>k;
//beolvasás
for(int i=0;i<k;++i)
{
int x,y,r;cin>>x>>y>>r;
Kor tt;
tt.i=i;tt.x=x;tt.y=y;tt.r=r;tt.upper=false;tt.lower=false;
t.pb(tt);
}
//felső és alsó körök/csúcsok meghatározása
for(int j=0;j<t.size();++j)
{
if(t[j].y-t[j].r<=0) t[j].upper=true;
if(t[j].y+t[j].r>=m) t[j].lower=true;
}
//mely körök/csúcsok között található él
for(int i=0;i<k;++i)
{
for(int j=i+1;j<k;++j)
{
double dist = ((t[i].x-t[j].x)*(t[i].x-t[j].x))+((t[i].y-t[j].y)*(t[i].y-t[j].y)); //(középpontok távolsága)^2
double maxdist = (t[i].r+t[j].r)*(t[i].r+t[j].r); //(élek távolsága)^2
if(dist<=maxdist) //van él
{
adj[i].pb(j);
adj[j].pb(i);
}
}
}
bool tt[105]; //jártunk már-e a csúcsban
for(int j=0;j<105;++j) tt[j]=false;
bool vezet=true;
for(int i=0;i<k&&vezet;++i) //körökön végig megyünk...
{
if(t[i].upper && !tt[i]) //akkor keresünk kapcsolatot alsó csúccsal, ha felső csúcsnál vagyunk és még nem jártunk ebben a felső csúcsban.
{
tt[i]=true; //már jártunk itt...
if(searchforlower(i, tt)) vezet=false; //ha találunk utat: "nem vezet"
}
}
cout<<(vezet?"Vezet":"Nem vezet")<<"\n";
return 0;
}
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"
Nem vezet
Elvárt kimenet:Nem vezet
Ellenőrző kimenete:ok 2 tokens
Vezet
Elvárt kimenet:Vezet
Ellenőrző kimenete:ok "Vezet"