求助凸包
查看原帖
求助凸包
394167
Cure_Wing楼主2024/4/24 15:05

我写的是直接找到左下角的点直接极角排序,但是答案错误了,为什么呢?

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using std::cin;using std::cout;
constexpr int N=100005;
int t,n,u,v,m;
char c;
struct A{int x,y;}a[N];
inline long long len2(A x){return 1ll*x.x*x.x+1ll*x.y*x.y;}
inline A operator-(A a,A b){return A{a.x-b.x,a.y-b.y};}
inline long long Cross(A x,A y){return 1ll*x.x*y.y-1ll*x.y*y.x;}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	for(cin>>t;t--;){
		cin>>n;m=0;for(int i=1;i<=n;++i){cin>>u>>v>>c;if(c=='Y') a[++m]=A{u,v};}
		std::sort(a+1,a+m+1,[](A a,A b){if(a.x!=b.x) return a.x<b.x;return a.y<b.y;});
		std::sort(a+2,a+m+1,[](A c,A d){if(Cross(c-a[1],d-a[1])) return Cross(c-a[1],d-a[1])>0;return len2(c-a[1])<len2(d-a[1]);});
		cout<<m<<'\n';for(int i=1;i<=m;++i) cout<<a[i].x<<' '<<a[i].y<<'\n';
	}
	return 0;
}
2024/4/24 15:05
加载中...