https://llvm.org/bugs/show_bug.cgi?id=26269
Bug ID: 26269
Summary: Quick sort return false result
Product: libc++
Version: 3.8
Hardware: Macintosh
OS: MacOS X
Status: NEW
Severity: normal
Priority: P
Component: All Bugs
Assignee: unassignedclangb...@nondot.org
Reporter: teg...@live.cn
CC: llvm-bugs@lists.llvm.org, mclow.li...@gmail.com
Classification: Unclassified
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.
--
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
