編輯:關於Android編程
題目鏈接:Codeforces 437E The Child and Polygon
題目大意:給出一個多邊形,問說有多少種分割方法,將多邊形分割為多個三角形。
解題思路:首先要理解向量叉積的性質,一開始將給出的點轉換成順時針,然後用區間dp計算。dp[i][j]表示從點i到點j可以有dp[i][j]種切割方法。然後點i和點j是否可以做為切割線,要經過判斷,即在i和j中選擇的話點k的話,點k要在i,j的逆時針方。
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 205;
const ll MOD = 1e9+7;
struct point {
ll x, y;
ll operator * (const point& c) const {
return x * c.y - y * c.x;
}
point operator - (const point& c) const {
point u;
u.x = x - c.x;
u.y = y - c.y;
return u;
}
}p[N];
int n;
ll dp[N][N];
void init () {
scanf("%d", &n);
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; i++)
scanf("%lld %lld", &p[i].x, &p[i].y);
ll tmp = 0;
p[n] = p[0];
for (int i = 0; i < n; i++)
tmp += p[i] * p[i+1];
if (tmp < 0)
reverse(p, p + n);
}
ll solve (int l, int r) {
if (dp[l][r] != -1)
return dp[l][r];
ll& ans = dp[l][r];
ans = 0;
if (r - l == 1)
return ans = 1;
for (int i = l + 1; i < r; i++) {
if ((p[l] - p[r]) * (p[i] - p[r]) > 0)
ans = (ans + solve(l, i) * solve(i, r)) % MOD;
}
return ans;
}
int main () {
init();
printf("%lld\n", solve(0, n-1));
return 0;
}
android-async-http開源項目可以是我們輕松的獲取網絡數據或者向服務器發送數據,使用起來非常簡單,關於android-async-http開源項目的介紹內
一、ExpandableListView介紹 一個垂直滾動的顯示兩個級別(Child,Group)列表項的視圖,列表項來自ExpandableListAdapter
在上一篇文章-安卓開發環境搭建中,我們創建並啟動了eclipse自帶的安卓模擬器,該模擬器不僅啟動慢,而且在使用過程中的反應速度也是出奇的差,經常出現卡機現象。為了解決這
意圖是指兩個UI主界面的轉換,要想了解意圖就必須學習ACtivity的生命周期 默認在UI界面顯示的為運行為運行狀態,而在後台的為onPause方法 主線: