gym 101081E
题意：给出一些点，按顺序连线会得到一个多边形。这些点是按顺时针或逆时针给出的，求这个多边形有多少个点对外的夹角 <= 180 。
tags：
1】首先判断这个多边形的给出点的顺序。 只要取最大的 y坐标 或 x坐标 点判断即可，因为在最上、下、左、右的点肯定是凸的。
2】判断两个向量 A 到 B 是顺还是逆。 cross(a,b) = ax * by - ay * bx = norm(a)* norm(b) * sin<a, b> 。叉乘的结果是正数，说明a到b是逆时针，反之顺时针。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 200005; int n, x[N], y[N]; int check(int mi) { int x1 = x[mi]-x[mi-1], y1 = y[mi]-y[mi-1]; int x2 = x[mi+1]-x[mi], y2 = y[mi+1]-y[mi]; if(x1*y2-y1*x2 > 0) return 1; else if(x1*y2-y1*x2 == 0) return 2; else return 0; } int main() { scanf("%d", &n); int my=-INF, mi; rep(i,1,n) { scanf("%d%d", &x[i], &y[i]); if(my<y[i]) my=y[i], mi=i; } x[0]=x[n], y[0]=y[n]; x[n+1]=x[1], y[n+1]=y[1]; bool flag=0; if(check(mi)) flag=1; int cnt1=0, cnt2=0, cnt3=0; rep(i,1,n) { int tmp = check(i); if(tmp==1) ++cnt1; else if(tmp==0) ++cnt2; else ++cnt3; } printf("%d ", flag==0 ? (cnt1+cnt3) : (cnt2+cnt3)); return 0; }