UVA 12123 - Magnetic Train Tracks（计数问题）
浏览数：36 /
时间：2015年06月09日
题目链接：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;
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
