本文共 1191 字，大约阅读时间需要 3 分钟。
发现需要求一个下凸的半平面上有几个交点。
然后我们把它变成凸包的问题。
好写、好调、还没有精度误差。
#include #include #include #include #include #include #include #include using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define ll long long struct Vector{ int x,y; void print() { printf("Vector - > (%d,%d)\n",x,y); }}; struct Point{ int x,y; int id; void print() { printf("Point ID %d (%d,%d)\n",id,x,y); }}; Vector operator - (Point a,Point b){Vector ret;ret.x=a.x-b.x;ret.y=a.y-b.y;return ret;} ll operator * (Vector a,Vector b){return (ll)a.x*b.y-(ll)a.y*b.x;} int n,top=0;Point a[50005],sta[50005]; bool cmp(Point a,Point b){return a.x==b.x?a.y =2&&(sta[top]-sta[top-1])*(a[i]-sta[top])<=0) top--; sta[++top]=a[i]; } sort(sta+1,sta+top+1,cmp2); F(i,1,top) printf("%d ",sta[i].id); printf("\n");} void Finout(){ freopen("bzoj_1007.in","r",stdin); freopen("bzoj_1007.out","w",stdout);} int main(){// Finout(); scanf("%d",&n); F(i,1,n) { scanf("%d%d",&a[i].x,&a[i].y); a[i].y=-a[i].y; a[i].id=i; } sort(a+1,a+n+1,cmp); Andrew();}
转载于:https://www.cnblogs.com/SfailSth/p/6706277.html