8/19/2016
DesignandanalysisofalgorithmsCourse
X
achin.it1317@[Link]
Courses Designandanalysisofalgorithms
Announcements
Forum
Progress
Mentor
PrisonerEscape
Course
outline
Week1:
Introduction
Week1:
Analysisof
algorithms
Week1Quiz
Week2:
Searchingand
sorting
Week2Quiz
Dueon20160812,23:59IST
PrisonerEscape
(BalticOlympiadinInformatics,2009)
[Link]
thoroughlyplannedtheescapefromtheprisonitself,andafterthatthey
[Link],thevillage(markedasB,
seepicturebelow)andtheprison(markedasA)areseparatedbyacanyon
[Link]
rarelywalktherangeofviewofeachsoldierislimitedtoexactly100
[Link],dependingonthelocationsofsoldiers,itmaybepossibleto
passthecanyonsafely,keepingthedistancetotheclosestsoldierstrictly
largerthan100metersatanymoment.
Week2
Programming
Assignment
Week3:
Graphs
Week3Quiz
Week3
Programming
Assignment
Prisoner
Escape
Week4:
Weighted
graphs
Week4Quiz
Week4
Programming
Assignment
Youaretowriteaprogramwhich,giventhewidthandthelengthofthe
canyonandthecoordinatesofeverysoldierinthecanyon,andassuming
thatsoldiersdonotchangetheirlocations,determineswhetherprisoners
canpassthecanyonunnoticed.
SolutionHint
[Link]
[Link]
[Link]
Week5:Data
verticessandt,representingthenorthernandsouthernsideofthecanyon,
Structures:
[Link]
UnionFind
[Link]
andHeaps
searchorbreadthfirstsearchtocheckwhetherthereisapathbetweens
andtinG.
[Link]
1/5
8/19/2016
Week5:Divide
andConquer
Week5Quiz
Week5
Programming
Assignment
DesignandanalysisofalgorithmsCourse
andtinG.
Inputformat
ThefirstlinecontainsthreeintegersL,W,andNthelengthandthewidth
ofthecanyon,andthenumberofsoldiers,[Link]
followingNlinescontainsapairofintegersXiandYithecoordinatesofi
thsoldierinthecanyon(0XiL,0YiW).Thecoordinatesaregiven
inmeters,relativetothecanyon:thesouthwesterncornerofthecanyon
hascoordinates(0,0),andthenortheasterncornerofthecanyonhas
coordinates(L,W),[Link]
canyonmaystartatcoordinate(0,ys)forany0ysWandendat
coordinate(L,ye)forany0&\[Link]
integer.
Outputformat
Outputasingleinteger:0iftheprisonerscanescape,1iftheycannot.
Testdata
1W50,0001L50,0001N250
Example
Sampleinput1
1303405
1050
130130
70170
0180
60260
Sampleoutput1
1
Sampleinput2
5003004
2500
250300
100150
400150
Sampleoutput2
0
SampleTestCases
TestCase1
[Link]
Input
1303405
1050
130130
70170
Output
1
2/5
8/19/2016
DesignandanalysisofalgorithmsCourse
TestCase2
TestCase3
TestCase4
TestCase5
TestCase6
0180
60260
5003006
1000
100150
100300
4000
400150
400300
5003005
2500
250150
250300
100150
400150
5003004
2500
250300
100150
400150
5003005
5025
45025
100275
250120
400275
5003006
2500
100300
200150
300150
400300
250300
DueDateExceeded.Youscored100.0/100.
Yourlastrecordedsubmissionwas:
[Link]
3/5
8/19/2016
DesignandanalysisofalgorithmsCourse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<set>
#include<deque>
#include<list>
#include<utility>
usingnamespacestd;
#definesq(x)((x)*(x))
structpt:pair<int,int>
{
inti;
pt(intx=0,inty=0):pair<int,int>(x,y),i(1){}
};
intmain()
{
intL,W,n,r=100,d=2*r;
cin>>L>>W>>n;
set<pt>points;
typedefset<pt>::iteratoriter;
ptP;
list<int>G[n+2];
//PrepareGraphwithintelligence{usinglgnbasedset}
for(inti=1;i<=n;i++)
{
cin>>[Link]>>[Link];
P.i=i;
ptQ([Link],[Link]),R([Link]+d,[Link]+d);
iterl=points.lower_bound(Q),u=points.upper_bound(R);
for(iterj=l;j!=u;++j)//onlythosecircleswhichcanoverlap
if(sq([Link]>first)+sq([Link]>second)<=sq(d))
G[i].push_back(j>i),G[j>i].push_back(i);
if([Link]<=0)//ifPistouchingy=0
G[i].push_back(0),G[0].push_back(i);
if([Link]+r>=W)//ifPistouchingy=W
G[i].push_back(n+1),G[n+1].push_back(i);
[Link](P);
}
//DoDFS/BFStotrack
intvisited[n+2];
for(inti=0;i<n+2;i++)
visited[i]=0;
deque<int>q;
q.push_back(0);//they=0line
while(![Link]())
{
intv=[Link]();
q.pop_front();
if(visited[v])
continue;
visited[v]=1;
if(v==n+1)//they=Lline
{
cout<<1<<"\n";//thereisanpathfromy=0toy=L
return0;
}
for(list<int>::iteratori=G[v].begin();i!=G[v].end();++i)
q.push_back(*i);
}
cout<<0<<"\n";
return0;
}
End
[Link]
4/5
8/19/2016
DesignandanalysisofalgorithmsCourse
2014NPTELPrivacy&TermsHonorCodeFAQs
Aprojectof
Inassociationwith
Fundedby
Poweredby
[Link]
5/5
