Skip to content

Commit 2d41a82

Browse files
likecstcNickolas
likecs
authored and
tcNickolas
committed
Unify tags used for code sections to be ``` (cp-algorithms#116)
1 parent ee810e4 commit 2d41a82

20 files changed

Lines changed: 655 additions & 595 deletions

‎src/combinatorics/catalan-numbers.md‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,8 @@ $( ) ( ( ) )$ can be divided into $( )$ and $( ( ) )$, but cannot be divided int
4343

4444
#### C++ implementation <span class="toggle-code">Show/Hide</span>
4545

46-
<pre><code>const int MOD = ....
46+
```cpp
47+
const int MOD = ....
4748
const int MAX = ....
4849
int catalan[MAX];
4950
void init() {
@@ -57,7 +58,8 @@ void init() {
5758
}
5859
}
5960
}
60-
} </code></pre>
61+
}
62+
```
6163

6264
###Analytical formula
6365
$$C_n = \frac{1}{n + 1} C_{2n}^{n}$$

‎src/geometry/circle-line-intersection.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ Had we solved the original system of equations using algebraic methods, we would
4141

4242
As indicated at the outset, we assume that the circle is centered at the origin, and therefore the input to the program is the radius $r$ of the circle and the parameters $A$, $B$ and $C$ of the equation of the line.
4343

44-
~~~~~
44+
```cpp
4545
double r, a, b, c; // given as input
4646
double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
4747
if (c*c > r*r*(a*a+b*b)+EPS)
@@ -61,7 +61,7 @@ else {
6161
puts ("2 points");
6262
cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
6363
}
64-
~~~~~
64+
```
6565
6666
## Practice Problems
6767

‎src/geometry/length-of-segments-union.md‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,10 +12,11 @@ Store in an array $X$ the endpoints of all the segments sorted by its value, wit
1212

1313
## Implementation
1414

15-
<pre><code>unsigned segments_union_measure (const vector <pair <int,int> > & a)
15+
```cpp
16+
unsigned segments_union_measure (const vector < pair<int,bool> > & a)
1617
{
1718
unsigned n = a.size();
18-
vector <pair <int,bool> > x (n*2);
19+
vector < pair<int,bool> > x (n*2);
1920
for (unsigned i=0; i < n; i++)
2021
{
2122
x[i*2] = make_pair (a[i].first, false);
@@ -36,4 +37,5 @@ Store in an array $X$ the endpoints of all the segments sorted by its value, wit
3637
--c;
3738
}
3839
return result;
39-
}</code></pre>
40+
}
41+
```

‎src/geometry/oriented-triangle-area.md‎

Lines changed: 20 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -11,24 +11,26 @@ We can use the fact that a determinant of a $2\times 2$ matrix is equal to a sig
1111
$$2S=\left|\begin{matrix}x_2-x_1 & x_3-x_2\\\\y_2-y_1 & y_3-y_2\end{matrix}\right|=(x_2-x_1)(y_3-y_2)-(x_3-x_2)(y_2-y_1)$$
1212

1313
## Implementation
14-
15-
// twice the triangle's area
16-
int area_determinant (int x1, int y1, int x2, int y2, int x3, int y3) {
17-
return (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1);
18-
}
19-
20-
// unsigned area of the triangle
21-
double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) {
22-
return abs (area_determinant (x1, y1, x2, y2, x3, y3)) / 2.0;
23-
}
24-
25-
// two predicates for angle orientation
26-
bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
27-
return area_determinant (x1, y1, x2, y2, x3, y3) < 0;
28-
}
29-
bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
30-
return area_determinant (x1, y1, x2, y2, x3, y3) > 0;
31-
}
14+
```cpp
15+
// twice the triangle's area
16+
int area_determinant (int x1, int y1, int x2, int y2, int x3, int y3) {
17+
return (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1);
18+
}
19+
20+
// unsigned area of the triangle
21+
double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) {
22+
return abs (area_determinant (x1, y1, x2, y2, x3, y3)) / 2.0;
23+
}
24+
25+
// two predicates for angle orientation
26+
bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
27+
return area_determinant (x1, y1, x2, y2, x3, y3) < 0;
28+
}
29+
30+
bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) {
31+
return area_determinant (x1, y1, x2, y2, x3, y3) > 0;
32+
}
33+
```
3234
3335
## Practice Problems
3436
* [Codechef - Chef and Polygons](https://www.codechef.com/problems/CHEFPOLY)

‎src/graph/all-pair-shortest-path-floyd-warshall.md‎

Lines changed: 31 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -24,15 +24,17 @@ Before $k^{th}$ phase $( k = 1 ... n )$, the $d[i][j]$ for any vertices $i$ and
2424
In other words, before $k^{th}$ phase the value of $d[i][j]$ is equal to the length of the shortest path from vertex $i$ to the vertex $j$, if this path is allowed to enter only the vertex with numbers smaller $k$ (the beginning and end of the path are not restricted by this property).
2525

2626
It is easy to make sure that this property holds for the first phase. For $k = 0$, we can fill matrix as:
27-
28-
/* Assuming weight(i, j) is the cost of the direct edge from the vertex i to the vertex j
29-
weight(i ,j) = 0 if no edge between vertex i and vertex j exits and
30-
weight(i, j) is non-zero if the edge between vertex i and vertex j exists */
31-
32-
if ( weight(i, j) != 0) // direct edge between i and j exists
33-
d[i][j] = weight(i, j);
34-
else // direct edge between i and j does not exist
35-
d[i][j] = INF;
27+
28+
```cpp
29+
/* Assuming weight(i, j) is the cost of the direct edge from the vertex i to the vertex j
30+
weight(i ,j) = 0 if no edge between vertex i and vertex j exits and
31+
weight(i, j) is non-zero if the edge between vertex i and vertex j exists */
32+
33+
if ( weight(i, j) != 0) // direct edge between i and j exists
34+
d[i][j] = weight(i, j);
35+
else // direct edge between i and j does not exist
36+
d[i][j] = INF;
37+
```
3638

3739
At the same time, if there is no edge from $i$ to $j$, $d[i][j]$ should be $\infty$ (some high positive value denoting infinity). As we shall see later, it is a requirement for the algorithm.
3840

@@ -50,7 +52,9 @@ Suppose now that we are in the $k^{th}$ phase, and we want to compute the matrix
5052

5153
Combining these two cases, we find that $k^{th}$ phase is required to recalculate the length of the shortest paths between all pairs of vertices $i$ and $j$ in the following way:
5254

53-
new_d[i][j] = min ( d[i][j] , d[i][k] + d[k][j] ) ;
55+
```cpp
56+
new_d[i][j] = min ( d[i][j] , d[i][k] + d[k][j] ) ;
57+
```
5458

5559
Thus, all the work that is required to produce $k^{th}$ phase is to iterate over all pairs of vertices and recalculate the length of the shortest path between them. As a result, after the $n^{th}$ phase, in the Distance Matrix, the value of $d[i][j]$ is the length of the shortest path between pair of vertices $i$ and $j$, or, is $\infty$ if the path between the vertices $i$ and $j$ does not exist.
5660

@@ -64,20 +68,24 @@ Let $d[][]$ is a $2-D$ array of size n x n, which is filled according to the $0^
6468

6569
It is required to have $d[i][i] = 0$ for any $i$ at the $0^{th}$ phase.
6670

67-
for ( int k = 0 ; k < n ; ++k )
68-
for ( int i = 0 ; i < n ; ++i )
69-
for ( int j = 0 ; j < n ; ++j )
70-
d[i][j] = min ( d[i][j] , d[i][k] + d[k][j] ) ;
71+
```cpp
72+
for ( int k = 0 ; k < n ; ++k )
73+
for ( int i = 0 ; i < n ; ++i )
74+
for ( int j = 0 ; j < n ; ++j )
75+
d[i][j] = min ( d[i][j] , d[i][k] + d[k][j] ) ;
76+
```
7177

7278
It is assumed that if there is no edge between two any vertices $i$ and $j$, the adjacency matrix at $d[i][j]$ contains a large number (large enough so that it is greater than the length of any path in this graph), then this edge will always be unprofitable to take, and the algorithm will work correctly.
7379

7480
However, in the presence of negative weight edges in the graph, special measures are not taken, the resulting values in matrix may appear of the form $\infty - 1$, $\infty - 2$, etc., which, of course, still indicates that between the respective vertices no path at all exists. Therefore, if the graph is having negative weight edges, it is better to write Floyd-Warshall algorithm in the following way, so that it does not perform transitions from states, which already are "non-existence of the path":
7581

76-
for ( int k = 0 ; k < n ; ++k )
77-
for ( int i = 0 ; i < n ; ++i )
78-
for ( int j = 0 ; j < n ; ++j )
79-
if ( d [i][k] < INF && d [k][j] < INF )
80-
d[i][j] = min ( d[i][j] , d[i][k] + d[k][j] ) ;
82+
```cpp
83+
for ( int k = 0 ; k < n ; ++k )
84+
for ( int i = 0 ; i < n ; ++i )
85+
for ( int j = 0 ; j < n ; ++j )
86+
if ( d [i][k] < INF && d [k][j] < INF )
87+
d[i][j] = min ( d[i][j] , d[i][k] + d[k][j] ) ;
88+
```
8189

8290
## Retrieving the sequence of vertices in the shortest path
8391

@@ -93,8 +101,10 @@ With respect to the Floyd-Warshall Algorithm, the unpleasant effects of the real
93101

94102
To avoid this, the can be modified to take the error(EPS = $\Delta$) into account, by using following type of comparison:
95103

96-
if ( d[i][k] + d[k][j] < d[i][j] - EPS )
97-
d[i][j] = d[i][k] + d[k][j] ;
104+
```cpp
105+
if ( d[i][k] + d[k][j] < d[i][j] - EPS )
106+
d[i][j] = d[i][k] + d[k][j] ;
107+
```
98108

99109
## The case of negative cycles
100110

0 commit comments

Comments
 (0)