程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3629 Convex(計數問題)

hdu 3629 Convex(計數問題)

編輯:C++入門知識

題目鏈接:hdu 3269 Convex

題目大意:給出n個點,問任選四個點可以組成多少個凸四邊形。

解題思路:和uav11529的做法是一樣的,只不過求的東西不一樣。

#include 
#include 
#include 
#include 
#include 

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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved