首页 > 代码库 > hdu 3629 Convex(计数问题)
hdu 3629 Convex(计数问题)
题目链接:hdu 3269 Convex
题目大意:给出n个点,问任选四个点可以组成多少个凸四边形。
解题思路:和uav11529的做法是一样的,只不过求的东西不一样。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1205;
const double pi = 4 * atan(1.0);
const double eps = 1e-9;
int n;
ll s;
double r[2*N];
struct point {
double x, y;
}p[N];
ll Count (int d) {
int c = 0, mv = 0;
for (int i = 0; i < n; i++) {
if (i == d)
continue;
double a = atan2(p[i].y-p[d].y, p[i].x-p[d].x);
r[c] = a;
r[c+n-1] = a + 2*pi;
c++;
}
c = 2 * n - 2;
sort(r, r + c);
ll ans = 0;
for (int i = 0; i < n-1; i++) {
double tmp = r[i] + pi;
while (tmp > r[mv])
mv++;
ll cnt = mv - i - 1;
ans = ans + cnt * (cnt-1) / 2;
}
return s - ans;
}
ll solve () {
s = (n-1) * (n-2) * (n-3) / 6;
ll c = s * n / 4;
ll ans = 0;
for (int i = 0; i < n; i++)
ans += Count(i);
return c - ans;
}
int main () {
int cas;
cin >> cas;
while (cas--) {
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
cout << solve() << endl;
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。