ecnu 3059. 极坐标排序

淡淡的烟草味﹌ 2022-10-06 00:56 140阅读 0赞

[题目][Link 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

double判断相等以及大于小于 用1e-7才可以过

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    #define great(x,y) ( (x)-(y) ) > 1e-7
    #define less(x,y) ( (x)-(y) ) < -1e-7
    #define eq(x,y) abs( (x)-(y) ) <= 1e-7

#include <iostream>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    #include <stdio.h>
    
    using namespace std;
    
    #pragma warning(disable:4996)
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    #define great(x,y) ( (x)-(y) ) > 1e-7
    #define less(x,y) ( (x)-(y) ) < -1e-7
    #define eq(x,y) abs( (x)-(y) ) <= 1e-7
    
    
    using ll = long long;
    
    struct pos { 
    	double x, y;
    	double r2;
    	double r;
    	double du;
    	
    };
    bool solve(int cn) { 
    
    	int n;
    	cin >> n;
    	vector<pos> arr(n);
    	double pi = 3.1415926;
    
    	arr.reserve(n);
    	for (int i = 0; i < n; ++i) { 
    		cin >> arr[i].x;
    		cin >> arr[i].y;
    		arr[i].r2 = arr[i].x * arr[i].x + arr[i].y * arr[i].y;
    		arr[i].r = sqrtl(arr[i].r2);
    
    		double du = acos(arr[i].x / arr[i].r);
    		if (arr[i].y >= 0) { 
    			arr[i].du = du;
    		}else{ 
    			arr[i].du = 2*pi - du;
    		}
    		
    	}
    
    	auto cmp = [&](const pos& a, const pos& b) { 
    		if( eq(a.du,b.du)){ 
    			return a.r2 > b.r2;
    		}else{ 
    			return less(a.du, b.du);
    		}
    	};
    	sort(arr.begin(),arr.end(),cmp);
    	cout << "case #" << cn << ":"<<endl;
    
    	for (auto i : arr) { 
    		printf("(%.4lf,%.4lf)\n", i.r, i.du);
    	}
    	return true;
    }
    
    int main() { 
    
    	//freopen("../in1.txt","r",stdin);
    
    	int t;
    	cin >> t;
    
    	for (int i = 0; i < t; ++i) { 
    		solve(i);
    	}
    	return 0;
    }

![在这里插入图片描述][20210610153529809.png]

[Link 1]: https://acm.ecnu.edu.cn/problem/3059/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221005/145517060e114c74a56e32b871f29e90.png
[20210610153529809.png]: /images/20221005/8aaf920a1c724eed9028dc3e360dc0e3.png