简单凸包。处理凸包的时候吧ch写成了pt，wa了两次。
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 struct Point {10 double x, y;11 Point() {}12 Point(double x, double y) : x(x), y(y) {}13 } ;14 15 bool operator < (Point x, Point y) { return x.x < y.x || (x.x == y.x && x.y < y.y);}16 bool operator == (Point x, Point y) { return x.x == y.x && x.y == y.y;}17 Point operator - (Point x, Point y) { return Point(x.x - y.x, x.y - y.y);}18 19 const double EPS = 1e-8;20 inline int sgn(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1);}21 inline double crossDet(Point x, Point y) { return x.x * y.y - x.y * y.x;}22 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}23 24 int andrew(Point *pt, int n, Point *ch) {25 sort(pt, pt + n);26 n = (int) (unique(pt, pt + n) - pt);27 int m = 0;28 for (int i = 0; i < n; i++) {29 while (m > 1 && sgn(crossDet(ch[m - 2], ch[m - 1], pt[i])) <= 0) m--;30 ch[m++] = pt[i];31 }32 int k = m;33 for (int i = n - 2; i >= 0; i--) {34 while (m > k && sgn(crossDet(ch[m - 2], ch[m - 1], pt[i])) <= 0) m--;35 ch[m++] = pt[i];36 }37 if (n > 1) m--;38 return m;39 }40 41 const int N = 111111;42 Point pt[N], ch[N];43 const double PI = acos(-1.0);44 45 inline double angle(Point x) { return atan2(x.y, x.x);}46 47 int main() {48 // freopen("in", "r", stdin);49 int T, n;50 cin >> T;51 for (int cas = 1; cas <= T; cas++) {52 cin >> n;53 for (int i = 0; i < n; i++) {54 scanf("%lf%lf", &pt[i].x, &pt[i].y);55 }56 if (n <= 2) {57 printf("Case %d: 0.00000000\n", cas);58 continue;59 }60 n = andrew(pt, n, ch);61 for (int i = 0; i < 10; i++) {62 ch[i + n] = ch[i];63 }64 double mini = 1e10;65 for (int i = 0; i < n; i++) {66 double ang1 = angle(ch[i] - ch[i + 1]);67 double ang2 = angle(ch[i + 2] - ch[i + 1]);68 double da = fabs(ang1 - ang2);69 if (da > PI) da = 2.0 * PI - da;70 mini = min(mini, da * 180.0 / PI);71 }72 printf("Case %d: %.8f\n", cas, mini);73 }74 return 0;75 }
——written by Lyon