OJ Board

I am getting RTE on this problem.I tried to implement bentley ottmann algorithm.I know this problem can be solved in O(n^2) but i wanted to check correctness of my implemented bentley ottmann.Can anyone provide me some test cases? #include <bits/stdc++.h> #define EPS 1e-9 using namespace std; struct...

What are some straight forward sweep line problems?

I am getting wrong answer for this problem.Can anyone figure out where is the problem? #include <bits/stdc++.h> #define EPS 1e-9 #define pi acos(-1) using namespace std; struct point { //***when points are double double x,y,angle; point() { x=0; y=0; angle=0; } //sort points first with respect to x ...

Can i assume the recangle lines are parallel to axis?

WA.Need some test cases. #include <bits/stdc++.h> using namespace std; int manh[45][45],grid[45],n,bound; int man() { int r1,c1,r2,c2,i,j; for(i=1;i<=41;i++) { r1=(i-1)/4; r1++; c1=i%4; if(c1==0) c1=4; for(j=1;j<=41;j++) { r2=(j-1)/4; r2++; c2=j%4; if(c2==0) c2=4; manh[i][j]=abs(r1-r2)+abs(c1-c2); }...

I thought it was an adhoc but getting WA.Where is the problem? //#include <bits/stdc++.h> #include<cstdio> #include<sstream> #include<cstdlib> #include<cctype> #include<cmath> #include<algorithm> #include<set> #include<queue> #include<stack> #include<list> #include<iostream> #include<fstream> #inclu...

WA and the only testcase given by brianfry is too big to debug. #include<cstdio> #include<sstream> #include<cstdlib> #include<cctype> #include<cmath> #include<algorithm> #include<set> #include<queue> #include<stack> #include<list> #include<iostream> #include<fstream> #include<numeric> #include<strin...

Because thats what came to my mind at first glance @brianfry713

Getting TLE....is this problem solvable with bitmask?? i counted current position and previous combination of (1,2) as my dp state.Here is my code. #include<cstdio> #include<sstream> #include<cstdlib> #include<cctype> #include<cmath> #include<algorithm> #include<set> #include<queue> #include<stack> ...

Is there anyway to solve the problem by running dijkstra's algo only once instead of placing firestation at every possible intersection?

Is it not a ad hoc? My technique was to start with a node with lowest degree and traverse the graph by dfs.If at any node i do not find any new edges to explore i will return to its paernt only if the parent still has any new node to explore.That is how i calculated minimum no of edges to travel in ...

At first i thought it is an easy problem but struggling for past two days.Is modification of dijkstras algo enough to get AC?Or do i have to know k'th shortest path algo(yen's algo) or floyd's modification?

Thanks brianfry713,you always help .Struggled to find out worse roots but at last ACED.

That's why i asked whether is it possible that there is a forest instead of a tree in input.Even your output differs from the output i got herehttp://www.udebug.com/UVa/10459... I do not think there is any input where any node is isolated.

Is the given tree connected or could there be any forest???Getting Wa... Passed all I/O of the forum when the tree is connected,here is my code