題目鏈接

題目描述

Rabbit和xxx獲得了一個(gè)很大的蛋糕，這個(gè)蛋糕實(shí)際上是由N個(gè)點(diǎn)組成的凸多邊形(點(diǎn)從1到N編號(hào),保證沒(méi)有三點(diǎn)共線)。
接著兩個(gè)人開(kāi)始分蛋糕，他們準(zhǔn)備沿著蛋糕上兩點(diǎn)連成的直線把蛋糕切成兩份，由于Rabbit是女生，xxx總會(huì)把大的那一份分給Rabbit。現(xiàn)在有Q種切的方案，xxx可以選擇任意一種，問(wèn)xxx最多能分得多少蛋糕？

輸入描述:

第一行兩個(gè)整數(shù)N，Q。
接下來(lái)N行，每行兩個(gè)數(shù)xi，yi表示第i個(gè)點(diǎn)的坐標(biāo)(點(diǎn)按逆時(shí)針順序給出)。
接下來(lái)Q行，每行兩個(gè)整數(shù)S，T表示切的兩個(gè)點(diǎn)。

輸出描述:

輸出xxx最多能分得多少面積的蛋糕。

輸入

4 2
0.5 0.5
10.5 0.5
10.5 10.5
0.5 10.5
1 3
4 2

輸出

50.00

思路

• 暴力枚舉TLE

• 記錄從起點(diǎn)到每個(gè)點(diǎn)的面積，這樣任意平分的面積就可以表示：
  
  S3 = S - S1 - S2

• 叉積求面積：
  

#include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define REP(i, n) for (int i = 1; i <= (n); ++i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define maxn 100005 using namespace std; struct ac{double x, y;friend double operator * (const ac t1, const ac t2) {double sum = t1.x * t2.y - t1.y * t2.x;return abs(sum);}friend ac operator - (const ac t1, const ac t2) {return {t1.x - t2.x, t1.y - t2.y};} }a[maxn]; int N, Q; double pre[maxn];int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); #endifscanf("%d %d", &N, &Q);pre[1] = pre[2] = 0;REP (i, N) {scanf("%lf %lf", &a[i].x, &a[i].y);if (i >= 3) {pre[i] = pre[i-1] + (a[1] - a[i-1]) * (a[1] - a[i]);}}double ans = 0.0;rep (i, Q) {int S, T;scanf("%d %d", &S, &T);if (S > T) swap(S, T);double sum = pre[T] - pre[S] - (a[1] - a[S]) * (a[1] - a[T]);sum = min(sum, pre[N] - sum);ans = max(sum, ans);}printf("%.10lf\n", ans / 2);return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛36 F-Rabbit的蛋糕 (叉积求面积, 记录前缀)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。