<html>
<head>
<base href="https://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - Quick sort return false result"
href="https://llvm.org/bugs/show_bug.cgi?id=26269">26269</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Quick sort return false result
</td>
</tr>
<tr>
<th>Product</th>
<td>libc++
</td>
</tr>
<tr>
<th>Version</th>
<td>3.8
</td>
</tr>
<tr>
<th>Hardware</th>
<td>Macintosh
</td>
</tr>
<tr>
<th>OS</th>
<td>MacOS X
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>All Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>tegusi@live.cn
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org, mclow.lists@gmail.com
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>I wrote a code like that:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
#define mk make_pair
using namespace std;
const int SIZE = 1010;
const double Eps = 1e-6;
typedef pair<double, double>II;
II orig;
II data[SIZE];
int N;
void Read() {
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%lf%lf", &data[i].x, &data[i].y);
}
II operator -(II A, II B){return mk(A.x - B.x, A.y - B.y);}
II operator +(II A, II B){return mk(A.x + B.x, A.y + B.y);}
II operator *(II A, double k){return mk(A.x * k, A.y * k);}
double calc_length(II A){return sqrt(A.x * A.x + A.y * A.y);}
double pd(double x) {
if (x > Eps) return 1;
if (x < -Eps) return -1;
return 0;
}
int Get_quadrant(II A) {
if (pd(A.x) > 0 && pd(A.y) >= 0) return 1; //[0, 90)
if (pd(A.x) <= 0 && pd(A.y) > 0) return 2; //[90, 180)
if (pd(A.x) < 0 && pd(A.y) <= 0) return 3; //[180, 270)
if (pd(A.x) >= 0 && pd(A.y) < 0) return 4; //[270, 360)
return 0;
}
double cross(II p0, II p1, II p2) {
return (p1.x - p0.x) * (p2.y - p0.y) -
(p2.x - p0.x) * (p1.y - p0.y);
}
bool polar_angle_cmp(II A, II B) {
if (pd(A.x - orig.x) == 0 && pd(A.y - orig.y) == 0) return true;
if (pd(B.x - orig.x) == 0 && pd(B.y - orig.y) == 0) return false;
int t1 = Get_quadrant(A - orig);
int t2 = Get_quadrant(B - orig);
if (t1 != t2) return t1 < t2;
double sum = cross(orig, A, B);
if (pd(sum) != 0) return (pd(sum) > 0);
return calc_length(A - orig) < calc_length(B - orig);
}
bool cmp2(const int &A, const int &B) {
return A <= B;
}
int main() {
//freopen("t.in", "r", stdin);
//freopen("t.out", "w", stdout);
Read();
orig.x = orig.y = 0;
sort(data + 1, data + 1 + N, polar_angle_cmp);
for (int i = 1; i <= N; i++)
printf("%lf %lf\n", data[i].x, data[i].y);
return 0;
}
My input is as followed:
21
6 3
8 4
0 3
0 6
0 0
-1 3
-3 1
0 0
-2 0
0 0
-3 -2
-1 -3
0 -3
2 -3
0 0
3 -3
1 0
0 0
0 0
5 2
4 2
My ideal output should be:
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
1.000000 0.000000
5.000000 2.000000
4.000000 2.000000
6.000000 3.000000
8.000000 4.000000
0.000000 3.000000
0.000000 6.000000
-1.000000 3.000000
-3.000000 1.000000
-2.000000 0.000000
-3.000000 -2.000000
-1.000000 -3.000000
0.000000 -3.000000
2.000000 -3.000000
3.000000 -3.000000
1.000000 0.000000 is after 0.000000 0.000000,
however, I got this when I compiled with libc++:
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
1.000000 0.000000 //strange line
0.000000 0.000000
5.000000 2.000000
4.000000 2.000000
6.000000 3.000000
8.000000 4.000000
0.000000 3.000000
0.000000 6.000000
-1.000000 3.000000
-3.000000 1.000000
-2.000000 0.000000
-3.000000 -2.000000
-1.000000 -3.000000
0.000000 -3.000000
2.000000 -3.000000
3.000000 -3.000000
Could you please fix it?
Thank you.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>