题目链接:12123 - Magnetic Train Tracks
题意:给定n个点,求有几个锐角三角形。
思路:和UVA 11529是同类的题,枚举一个做原点,然后剩下点根据这个原点进行极角排序,然后利用two pointer去遍历一遍,找出角度小于90度的锐角,然后扣掉这些得到钝角三角形的个数,然后在用总情况去扣掉钝角就是锐角或直角
代码:
#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; const double eps = 1e-9; const double pi = acos(-1.0); const int N = 1205; int n; struct Point { double x, y; void read() { scanf("%lf%lf", &x, &y); } } p[N]; double r[N * 2]; int C(int n, int m) { if (n < m) return 0; int ans = 1; for (int i = 0; i < m; i++) ans = ans * (n - i) / (i + 1); return ans; } double cal(Point a, Point b) { return atan2(b.y - a.y, b.x - a.x); } int solve(int num) { int tn = 0; for (int i = 0; i < n; i++) { if (i == num) continue; r[tn++] = cal(p[num], p[i]); } sort(r, r + tn); for (int i = 0; i < tn; i++) r[tn + i] = r[i] + 2 * pi; int j = 1; int ans = 0; for (int i = 0; i < tn; i++) { while (fabs(r[j] - r[i]) - pi / 2 <= -eps) j++; ans += j - i - 1; } return C(tn, 2) - ans; } int main() { int cas = 0; while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) p[i].read(); int ans = 0; for (int i = 0; i < n; i++) ans += solve(i); printf("Scenario %d:\n", ++cas); printf("There are %d sites for making valid tracks\n", C(n, 3) - ans); } return 0; }