Ch4ot1c_M@dn3ss

6213

wuno
Woo.
99的手速加上1的运气
jjl0906
yydsw2x
FiloTimo
alter-c
acwing_gza
itdef
AC不了怎么办

zwling

sealt
1.1

hbin_frooog

sprx

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 5E5 + 5;
int n, m;
int w[N];

struct node {
int l, r;
int sum, f_sum, pre_sum, suf_sum;
}tr[N << 2];

inline void pushu(node &fa, node &l, node &r) {
fa.sum = l.sum + r.sum;
fa.pre_sum = max(l.pre_sum, l.sum + r.pre_sum);
fa.suf_sum = max(r.suf_sum, r.sum + l.suf_sum);
fa.f_sum = max({l.f_sum, r.f_sum, l.suf_sum + r.pre_sum});
}

inline void up(int u) {
pushu(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
if(l == r) tr[u] = {l, r, w[l], w[l], w[r], w[r]};
else {
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid),
build(u << 1 | 1, 1 + mid, r);
up(u);
}
}

void modify(int u, int x, int v) {      // 单点修改
if(tr[u].l == x and tr[u].r == x) tr[u] = {x, x, v, v, v, v};
else {
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
up(u);
}
}

node query(int u, int l, int r) {

if(tr[u].l >= l and tr[u].r <= r) return tr[u];
else
{
int mid = tr[u].l + tr[u].r >> 1;

if(r <= mid)return  query(u << 1, l , r);
else if(mid < l)return query(u << 1 | 1, l , r);

else {      // 横跨的部分
auto L = query(u << 1, l , r),
R = query(u << 1 | 1, l , r);
node res;
pushu(res, L, R);

return res;
}
}
}

int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
build(1, 1, n);

int op, x, y;
while(m--) {
scanf("%d %d %d", &op, &x, &y);
if(op == 1)
{
if(x > y) swap(x, y);
printf("%d\n", query(1, x, y).f_sum);
}
else modify(1, x, y);
}
return 0;
}



#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 5505;
int l[N], r[N],
u[N], d[N];

int cnt_1[N], row[N], col[N], idx;
int n, m;
int res[N], top;

void init() {
for(int i = 0; i <= m; ++i)
{
l[i] = i - 1,
r[i] = i + 1;
u[i] = d[i] = i;        // 上下都还是自己
}
l[0] = m, r[m] = 0;         // 重新设置边界的情况
idx = m + 1;                // 设置点的总数
}

void add(int &hh, int &tt, int x, int y) {
row[idx] = x, col[idx] = y; // 新增点
cnt_1[y] ++;

u[idx] = y, d[idx] = d[y],
u[d[y]] = idx, d[y] = idx;

r[hh] = l[tt] = idx,
r[idx] = tt, l[idx] = hh;
tt = idx ++;
}

void Remove(int p) {
r[l[p]] = r[p],
l[r[p]] = l[p];

for(int i = d[p]; i != p; i = d[i])
for(int j = r[i]; j != i; j = r[j])
{
cnt_1[col[j]] --;
u[d[j]] = u[j],
d[u[j]] = d[j];
}
}

void Remake(int p) {

for(int i = u[p]; i != p; i = u[i])
for(int j = l[i]; j != i; j = l[j])
{
u[d[j]] = j,
d[u[j]] = j;
cnt_1[col[j]] ++;
}
r[l[p]] = p,
l[r[p]] = p;
}

bool dfs() {
if(!r[0]) return 1;
int p = r[0];
for(int i = r[0]; i ; i = r[i])
if(cnt_1[i] < cnt_1[p]) // 挑出 1 最少的列
p = i;

Remove(p);
for(int i = d[p]; i != p; i = d[i])
{
res[++top] = row[i];
for(int j = r[i]; j != i; j = r[j]) Remove(col[j]);
if(dfs()) return 1;
for(int j = l[i]; j != i; j = l[j]) Remake(col[j]); // 恢复状态
top--;
}
Remake(p);                                              // 回溯
return 0;
}

int main() {

scanf("%d %d", &n, &m);
init();

for(int i = 1; i <= n; i++)
{
int hh = idx, tt = idx;
for(int j = 1; j <= m; ++j)
{
int x;
scanf("%d", &x);
}
}

if(dfs())
{
for(int i = 1; i <= top; ++i) printf("%d ", res[i]);
puts("");
}
else puts("No Solution!");
return 0;
}


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stdlib.h>

using namespace std;
int n;
const int N = 1010;
const double eps = 1e-7;

struct node {
int x, y ,r;
bool operator < (const node &a) const {
if(x - r != a.x - a.r) return x - r < a.x - a.r;
return r < a.r;
}
}cc[N];

inline int cmp(double x, double y) {
if(fabs(x - y) < eps) return 0;
return x < y ? -1 : 1;
}

using pdd = pair<double, double>;
pdd q[N];
vector<pdd>segx;

inline double f(double _x) {

int cnt = 0;
for(int i = 0; i < n; ++i)
{
double xx = fabs(_x - cc[i].x),
r = cc[i].r;

if(cmp(xx, r) < 0) {
double yy = sqrtl(r*r - xx*xx);
q[cnt++] = {cc[i].y - yy, cc[i].y + yy};
}
}
if(!cnt) return 0;

sort(q, q+cnt);
double res = 0;
double _y1 = q[0].first,
_y2 = q[0].second;

for(int i = 1; i < cnt; ++i)
{
if(_y2 >= q[i].first)
_y2 = max(_y2, q[i].second);
else
res += _y2 - _y1,
_y1 = q[i].first,
_y2 = q[i].second;
}
return res + _y2 - _y1;

}

inline double simpson(double l, double r) {
double mid = l / 2.0 + r / 2.0;                 // 积分部分
return (r - l) * (f(l) + f(r) + 4 * f(mid)) / 6;
}

double recursive_calc(double l, double r, double s) {
double mid = (r + l) / 2.00;
double _L = simpson(l, mid),
_R = simpson(mid, r);
if(!cmp(_L + _R, s))
return _L + _R;
return recursive_calc(l, mid, _L) +
recursive_calc(mid, r, _R);              // 递归调用部分
}

const int delta = 100;

void merge() {
sort(segx.begin(), segx.end());
vector<pdd> tmp;

double st = -1e20,
ed = -1e20;
for(auto p : segx)
{
if(cmp(p.first, ed) <= 0) ed = max(ed, p.second);
else {
if(cmp(st, -1e20)) tmp.push_back({st, ed});
st = p.first, ed = p.second;
}
}
tmp.push_back({st, ed});
segx = tmp;
}

int main() {
scanf("%d", &n);

for(int i = 0; i < n; ++i)
scanf("%d %d %d", &cc[i].x, &cc[i].y, &cc[i].r),
segx.push_back({cc[i].x - cc[i].r, cc[i].x + cc[i].r});

merge();
double res = 0;
for(auto p: segx)
res += recursive_calc(p.first, p.second,
simpson(p.first, p.second));

printf("%.3lf", res);
return 0;
}


// 好的数据结构，不应该写着写着就忘记最初要干什么
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
using ll = long long;

const int N = 5E5+10, inf = 1e9;
int n, m;

// 常数有点大
struct splay {      // 需要父节点得信息可以被两个孩子算出来
int son[2];     // 左右儿
int val;        // 当前节点的值
int size;       // 节点大小
int fa;         // 父节点

int rev;        // 整个区间是否翻转
int same;       // 整个区间是否要变成相同的数
// 两个的操作顺序对其它值得影响要考虑好，不然会很惨
// 此处记录得是操作之后的值

// 类似线段树的操作
int f_sum;      // 最大字段和

// 用来处理跨越区间的情况
int pre_sum,    // 最大前缀和
suf_sum;    // 最大后缀和
int sum;        // 区间和

void init(int _fa, int _val) {
son[0] = son[1] = 0;
size = 1;   fa = _fa;
val = _val;
rev = same = 0;

sum = f_sum = val;
pre_sum = suf_sum = max(0, val);
}
}tr[N];

int root, nodes[N], tt;
int w[N];

// 每个点维护的是一个序列
// 为了找到第 k 个数，还需要 size

// 首先需要把序列变成 splay
// 比较平衡的做法是通过递归建成二叉树

// 内存回收记得做一做
// 把点放到垃圾桶里，用的时候直接从垃圾桶要。

/**
*      套路：每次要操作区间的时候就把区间的前一个数和
*            后一个数记录下来，然后把前一个数转到根，
*            后一个数转到右儿子，那么待操作区间就在右儿子的左儿子上。
*            o
*             \
*              o
*             /
*           <>
*         <>ST<>
*        <><><><>
**/

void push_up(int x) {
auto &u = tr[x];
auto &l = tr[u.son[0]],
&r = tr[u.son[1]];
u.size = l.size + r.size + 1;       // 包含自己
u.sum = u.val + l.sum + r.sum;      // 所有值等于左 + 右 + 自己

// 按照原先构想更新标记
u.pre_sum = max(l.pre_sum, l.sum + u.val + r.pre_sum);
u.suf_sum = max(r.suf_sum, r.sum + u.val + l.suf_sum);
u.f_sum = max({l.f_sum, r.f_sum,
l.suf_sum + u.val + r.pre_sum});
}

inline void push_down(int x) {
auto &u = tr[x];
auto &l = tr[u.son[0]],
&r = tr[u.son[1]];
if(u.same) {
u.same = u.rev = 0;
if(u.son[0]) l.same = 1, l.val = u.val,
l.sum = l.val * l.size;
if(u.son[1]) r.same = 1, r.val = u.val,
r.sum = r.val * r.size;

if(u.val > 0)
{
if(u.son[0]) l.f_sum = l.pre_sum = l.suf_sum = l.sum;
if(u.son[1]) r.f_sum = r.pre_sum = r.suf_sum = r.sum;
}
else {
if(u.son[0]) l.f_sum = l.val, l.pre_sum = l.suf_sum = 0;
if(u.son[1]) r.f_sum = r.val, r.pre_sum = r.suf_sum = 0;

}
}
else if(u.rev) {
u.rev = 0;
l.rev ^= 1, r.rev ^= 1;
swap(l.pre_sum, l.suf_sum);
swap(r.pre_sum, r.suf_sum);
swap(l.son[1], l.son[0]);
swap(r.son[1], r.son[0]);
}
}

inline void rotate(int x) {        // 模板
int y = tr[x].fa;
int z = tr[y].fa;
int k = tr[y].son[1] == x;

tr[z].son[tr[z].son[1] == y] = x,
tr[x].fa = z;

tr[y].son[k] = tr[x].son[k ^ 1],
tr[tr[x].son[k ^ 1]].fa =y;

tr[x].son[k ^ 1] = y;
tr[y].fa = x;
push_up(y), push_up(x);
}

void splay(int x, int k) {          // 模板
while(tr[x].fa ^ k) {
int y = tr[x].fa,
z = tr[y].fa;
if(z ^ k)
if((tr[y].son[1] == x) ^ (tr[z].son[1] == y) )
rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root = x;
}

int get_k(int k) {                  // 模板
int ru = root;
while(ru) {
push_down(ru);
if(tr[tr[ru].son[0]].size >= k) ru = tr[ru].son[0];
else if(tr[tr[ru].son[0]].size + 1 == k) return ru;
else k -= tr[tr[ru].son[0]].size + 1,
ru = tr[ru].son[1];
}
}

int build (int l, int r, int fa)
{
int mid = l + r >> 1;
int ru = nodes[tt--];       // 从垃圾回收站里拿一个节点出来
tr[ru].init(fa, w[mid]);    // 初始化节点

if(l < mid) tr[ru].son[0] = build(l, mid - 1, ru);
if(mid < r) tr[ru].son[1] = build(mid + 1, r, ru);
push_up(ru);
return ru;

}

void meme_dfs(int u) {          // 垃圾回收，从原有的树上面薅下来
if(tr[u].son[0]) meme_dfs(tr[u].son[0]);
if(tr[u].son[1]) meme_dfs(tr[u].son[1]);
nodes[++tt] = u;
}

int main() {
for(int i = 1; i < N; i++)
nodes[++tt] = i;
scanf("%d %d", &n, &m);

tr[0].f_sum = -inf, w[0] = w[n + 1] = -inf;         // 初值还是要的
for(int i = 1; i <= n; i++) scanf("%d", w + i);
root = build(0, n + 1, 0);                          // 然后建树

char op[32];
while(m--)
{
scanf("%s", op);
if(!strcmp(op, "INSERT")) {
int posi, tot;
scanf("%d %d", &posi, &tot);
for(int i = 0; i < tot; ++i)
scanf("%d", w + i);
int l = get_k(posi + 1),
r = get_k(posi + 2);        // 因为是插入到后面
splay(l, 0), splay(r, l);       // 转成上面讲的方式

int u = build(0, tot - 1, r);

tr[r].son[0] = u;
push_up(r), push_up(l);
}
else if(!strcmp(op, "DELETE")) {
int posi, tot;
scanf("%d %d", &posi, &tot);

int l = get_k(posi),
r = get_k(posi + tot + 1);

splay(l, 0), splay(r, l);

meme_dfs(tr[r].son[0]);         // 转成上面讲的方式之后，直接回收孩子
tr[r].son[0] = 0;               // 简单置零就好
push_up(r), push_up(l);         // 然后将数据上传

}
else if(!strcmp(op, "MAKE-SAME")) {
int posi, tot, c;
scanf("%d %d %d", &posi, &tot, &c);

int l = get_k(posi),
r = get_k(posi + tot + 1);
splay(l, 0), splay(r, l);

auto &son = tr[tr[r].son[0]];                   // 左子树

son.same = 1, son.val = c, son.sum = c * son.size;
if(c > 0) son.f_sum = son.pre_sum = son.suf_sum = son.sum;
else son.f_sum = c, son.pre_sum = son.suf_sum = 0;

push_up(r), push_up(l);
}
else if(!strcmp(op, "REVERSE")) {
int posi, tot;
scanf("%d %d %d", &posi, &tot);

int l = get_k(posi),
r = get_k(posi + tot + 1);
splay(l, 0), splay(r, l);
auto &son = tr[tr[r].son[0]];

son.rev ^= 1;
swap(son.pre_sum, son.suf_sum);
swap(son.son[0], son.son[1]);
push_up(r), push_up(l);
}
else if(!strcmp(op, "GET-SUM")) {
int posi, tot;
scanf("%d %d %d", &posi, &tot);

int l = get_k(posi),
r = get_k(posi + tot + 1);
splay(l, 0), splay(r, l);
printf("%d\n", tr[tr[r].son[0]].sum);

}
else printf("%d\n",tr[root].f_sum);
}
return 0l;
}


#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 1E5 + 10;

int a[N];
int F, n;
/* 表述得不是太好 */
// 应该说只围成一块，围起来的地要大于等于 F 块
// 那么我们计算上就可以使用双指针来做完这件事情
double pre[N];

bool check(double x)        // 判断大多数方案是否能被满足
{
// 如何判断测算的平均值是可以的？首先拿所有值减去 x 然后算前缀和

for(int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + a[i] - x;
double minx = 2e9+10;
for(int i = 0, j = F; j <=n; j++, i++)
{
// 如何保证大于 F 块？
// 很简单，只要统计顺过去的最小值就可以保证
minx = min(minx, pre[i]);
if(pre[j] >= minx) return 1;    // 找到
}
return 0;               // 找不到
}

int main() {
// N 块地划分为至少 F 块地时，每块地包含的牛的平均值最大值
scanf("%d %d", &n, &F);

double l = 0, r = 0;
for(int i = 1; i <= n; ++i)
scanf("%d", a + i), r = max(r, (double)a[i]);

while(fabs(l - r) > 1e-6)
{
double mid = (l + r) / 2.0;
if(check(mid)) l = mid;     // 仍有进步空间
else r = mid;               // “进步过头”
}
printf("%lld", (long long)(r * 1000));
return 0;
}


bool check(double x)        // 判断大多数方案是否能被满足
{
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i] - x;
// 如何判断测算的平均值是可以的？首先拿所有值减去 x 然后算前缀和
double minx = 2e9, maxn = -2e9;
for(int i = F; i <= n; ++i)
{
minx = min(minx, (double)pre[i - F]);
maxn = max(maxn, (double)pre[i] - minx);
}
if(maxn >= 0) return 1;
return 0;               // 找不到
}


#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 1E5 + 10;

int a[N];
int F, n;
/* 表述得不是太好 */
// 应该说只围成一块，围起来的地要大于等于 F 块
// 那么我们计算上就可以使用双指针来做完这件事情
double pre[N];
using ld = long double;
using ll = long long;

inline ld k(int l, int r) {return (ld)(pre[r] - pre[l]) / (r - l);}

int q[N << 1];

int main() {
scanf("%d %d", &n, &F);
for(int i = 1; i <= n; ++i)
scanf("%d", a + i),
pre[i] = pre[i-1] + a[i];

/** 什么是平均数？
* (pre[i] - pre[i - F]) / F 就相当于是平均数，而且不难发现，分得越小对平均数越好。
* 那么，假定就一直在 F 取到。
* 如果是为了找最大值而特意去算这个式子，也就需要维护一个上凸包？
* 那么出列的条件依次是 队尾比上一个更劣，队头比下一个更劣。
* 可以公式化它们的关系。
**/

int head = 1, tail = 0;

ld res = 0.0L;
for(int i = F; i <= n; ++i)
{
int delta = i - F;
while (head < tail and k(q[tail], delta) <= k(q[tail - 1], delta))
tail--;
q[++tail] = delta;

}
printf("%lld", (ll)(res * 1000));
return 0;
}


• $O(n\log n)$：133ms
• $O(n)$：64ms

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>

/****************************************************************************************************
*   后缀数组 用倍增 nlogn 排完所有的后缀
*   需要：
*      排名为 i 的后缀的在原字符串中的次序                             @sa[i]
*      第 i 个后缀的排名                                               @rk[i]
*      排名为 i 和 i - 1 的最长公共前缀的值                            @height[i]
*      第 i 个后缀和排名在第 i 个后缀前面一位后缀的最长公共前缀长度    @h[i] = height[rk[i]]
*
*      对于字符串 aanklllv 而言
*      后缀有    v                     次序是      8
*                lv                                7
*                llv                               6
*                lllv                              5
*                klllv                             4
*                nklllv                            3
*                anklllv                           2
*                aanklllv                          1
****************************************************************************************************/

const int N = 1E6+10;
char str[N];
int sa[N], x[N], y[N], cnt[N];
int rk[N], height[N];
int n, m;

/* 映射关系有点复杂 */
void get_sa() {

/* 第一次基数排序 */
for(int i = 1; i <= n; ++i) cnt[x[i] = str[i]] ++;                  // 统计各字符的个数
// 并计算各个位置第一关键字离散化后是什么值
for(int i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];                   // 计算**字典序**下的，小于等于当前关键字的数量
for(int i = n; i; --i) sa[cnt[x[i]] --] = i;                        // 从后往前确定排序后排名在原字符串中的次序
// 并将关键字数量 --

// 做完基数排序后，视字符串后缀为有序后的比较。

for(int k = 1; k <= n; k <<= 1)                                     // 倍增
{
int num = 0;

for(int i = n - k + 1; i <= n; ++i) y[++num] = i;               // 第二关键字排名最小的部分（因为没有）
for(int i = 1 ; i <= n; ++i)
if(sa[i] > k)                                               // 某个后缀的第二关键字是另一个后缀的第一关键字
y[++num] = sa[i] - k;                                   // 要求某个后缀的位置要 > k
/* 计算第二关键字并按第二关键字排序 */

/* 第二次基数排序 */
for(int i = 1; i <= m; ++i) cnt[i] = 0;
for(int i = 1; i <= n; ++i) cnt[x[i]] ++;
for(int i = 2; i <= m; ++i) cnt[i] += cnt[i-1];
for(int i = n; i ; i--) sa[cnt[x[y[i]]]--] = y[i], y[i] = 0;    // 第二关键字来排，排完以后 y 没有用了

std::swap(x, y);                                                // 把 x 的信息存到 y 里
x[sa[1]] = 1, num = 1l;

for(int i = 2; i <= n; ++i)                                     // 离散化前 2k 个字符
x[sa[i]] = (y[sa[i - 1] + k] == y[sa[i] + k] &&
y[sa[i]] == y[sa[i - 1]]) ?
num : ++num;

if(num == n) break;                                             // 完全区别开所有后缀
m = num;                                                        // 不行就付给下一轮
}
}

void get_height() {                                                     // 最长公共前缀
for(int i = 1; i <= n; i ++) rk[sa[i]] = i;
for(int i = 1, k = 0; i <= n; ++i) {
if(rk[i] == 1) continue;
if(k) k--;
int j = sa[rk[i] - 1];
while(i + k <= n and j + k <= n and str[i + k] == str[j + k]) k++;
height[rk[i]] = k;
}
}

int main (){

scanf("%s", str + 1);
n = strlen(str + 1);
m = 122;

get_sa();
get_height();
for(int i = 1l; i <= n; ++i) printf("%d ", sa[i]);
puts("");
for(int i = 1l; i <= n; ++i) printf("%d ", height[i]);
return 0;
}


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
using db = long double;
const db pi = (db)acos(-1);
const int M = 3e5 + 10;
char sa[M], sb[M];
class cp
{
public:
db x, y;
cp(db xx = 0, db yy = 0) : x(xx), y(yy) {}
cp operator+(const cp &a) { return cp(a.x + x, y + a.y); }
cp operator-(const cp &a) { return cp(x - a.x, y - a.y); }
cp operator*(const cp &a) { return cp(x * a.x - y * a.y, x * a.y + y * a.x); }
} a[M];
int lena, lenb, tot, bits;
int rev[M];
int res[M];
void fft(cp a[], int len, int sig = 1)
{
for (int i = 0; i < len; ++i)
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int mid = 1; mid < len; mid <<= 1)
{
cp w(cos(pi / mid), sig * sin(pi / mid));
for (int i = 0; i < len; i += mid << 1)
{
cp w0(1, 0);
for (int j = 0; j < mid; j++, w0 = w0 * w)
{
auto x = a[i + j], y = w0 * a[i + j + mid];
a[i + j] = x + y, a[i + j + mid] = x - y;
}
}
}
}
int main()
{
scanf("%s%s", sa, sb);
lena = strlen(sa), lenb = strlen(sb);
int La = lena - 1, Lb = lenb - 1;
for (int i = 0; i < lena; ++i)
a[i].x = sa[La - i] - 48;
for (int i = 0; i < lenb; ++i)
a[i].y = sb[Lb - i] - 48;
while ((1 << bits) < lena + lenb)
bits++;
tot = 1 << bits;
for (int i = 0; i < tot; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bits - 1));
fft(a, tot);
for (int i = 0; i < tot; ++i)
a[i] = a[i] * a[i];
fft(a, tot, -1);
int t = 0, k = 0;
for (int i = 0; i < tot || t; ++i)
{
a[i].y /= 2.0 * tot; // 这里最需要去掉前导零。
t += a[i].y + 0.5;
res[k++] = t % 10;
t /= 10;
}
while (k - 1 > 0 and !res[k - 1])
k--;
for (int i = k - 1; ~i; --i)
printf("%d", res[i]);
return 0;
}


### 分析过程

#### 一

$$t=\int_0^{x_0}\sqrt{\dfrac{ 1 + (y’)^2}{2gy}}\mathrm{d}x$$

#### 二

$$I(\xi) = t = \int_0^{x_0}\bar{F}(x,\bar{y},\bar{y}’)\mathrm d x$$

$$\lim_{\xi \to 0}\dfrac{\mathrm d I(\xi)}{\mathrm d \xi} = \lim_{\xi \to 0}\Big(\dfrac{\mathrm d }{\mathrm d \xi}\int_0^{x_0}\bar{F}(x,\bar{y},\bar{y}’)\mathrm d x\Big) = \lim_{\xi \to 0}\int_0^{x_0}\dfrac{\mathrm d \bar{F}}{\mathrm d \xi}\mathrm d x = 0$$

$$\dfrac{\mathrm d \bar{F}}{\mathrm d \xi} = \dfrac{\partial \bar{F}}{\partial x}\cdot\dfrac{\partial x}{\partial \xi} + \dfrac{\partial \bar{F}}{\partial \bar{y}}\cdot\dfrac{\partial \bar{y}}{\partial \xi} + \dfrac{\partial \bar{F}}{\partial \bar{y}’}\cdot\dfrac{\partial \bar{y}’}{\partial \xi} = 0 + \eta\dfrac{\partial \bar{F}}{\partial \bar{y}} + \eta’\dfrac{\partial \bar{F}}{\partial \bar{y}’}$$

\begin{aligned}\lim_{\xi \to 0}\dfrac{\mathrm d I(\xi)}{\mathrm d \xi} &= \lim_{\xi \to 0}\int_0^{x_0} \eta\dfrac{\partial \bar{F}}{\partial \bar{y}} + \eta’\dfrac{\partial \bar{F}}{\partial \bar{y}’}\mathrm d x \\ &= \int_0^{x_0} \lim_{\xi \to 0}\Big(\eta\dfrac{\partial \bar{F}}{\partial (y + \xi\eta)} + \eta’\dfrac{\partial \bar{F}}{\partial (y’ + \xi\eta’)}\Big)\mathrm d x \\ \\ &= \int_0^{x_0}\Big( \eta\dfrac{\partial F}{\partial y} + \eta’\dfrac{\partial F}{\partial y’}\Big)\mathrm d x = \int_0^{x_0}\eta\dfrac{\partial F}{\partial y} \mathrm d x + \left. \eta\dfrac{\partial F}{\partial y’}\right|_0^{x_0} - \int_0^{x_0}\eta \mathrm d \dfrac{\partial F}{\partial y’} \\ &=\int_0^{x_0}\eta\Big(\dfrac{\partial F}{\partial y} - \dfrac{\mathrm d}{\mathrm d x }\dfrac{\partial F}{\partial y’}\Big) \mathrm d x + \color{red}{0} = 0\end{aligned}

#### 三

$$\dfrac{\mathrm d F}{\mathrm d x} = \dfrac{\partial F}{\partial x} + \dfrac{\partial F}{\partial y}\dfrac{\partial y}{\partial x} + \dfrac{\partial F}{\partial y’}\dfrac{\partial y’}{\partial x} = \dfrac{\partial F}{\partial x} + \dfrac{\partial F}{\partial y}y’ + \dfrac{\partial F}{\partial y’}y’'$$

$$\dfrac{\mathrm d}{\mathrm d x}\Big(F - y’\dfrac{\partial F}{\partial y’}\Big) = \dfrac{\partial F}{\partial x} + y’\Big( \dfrac{\partial F}{\partial y} - \dfrac{\mathrm d}{\mathrm d x}\dfrac{\partial F}{\partial y’}\Big)$$

#### 四

$$\sqrt{\dfrac{ 1 + (y’)^2}{2gy}} - y’\cdot\dfrac{2y’}{\sqrt{ 2gy}}\cdot\dfrac{1}{2\sqrt{ 1 + (y’)^2}}=\dfrac{1+(y’)^2 - (y’)^2}{\sqrt{ 2gy( 1 + (y’)^2)}} = C$$

$$\dfrac{\mathrm d y}{\sqrt{\dfrac{k-y}{y}}} = \mathrm d x$$

$$\dfrac{k}{2}\sqrt{\dfrac{1-\cos\theta}{1+\cos\theta}}\sin\theta\mathrm d \theta = \dfrac{k}{2}(1-\cos\theta)\mathrm d \theta = \mathrm d x$$

### 悬链线

$$y_\text{center} = \dfrac{\displaystyle\int_{0}^{L}f(x)\cdot\dfrac{m}{L} \mathrm{d}{s}}{m} = \dfrac{1}{L}\int_{-\frac{a}{2}}^{\frac{a}{2}} f(x)\sqrt{1+[f’(x)]^2} \mathrm{d}{x}$$

$$f(x)\sqrt{1+[f’(x)]^2} - f(x)\dfrac{[f’(x)]^2}{\sqrt{1+[f’(x)]^2}}=\dfrac{f(x)}{\sqrt{1+[f’(x)]^2}}=C$$

$$\dfrac{\mathrm d f(x)}{\mathrm d x}=\sqrt{\dfrac{[f(x)]^2 - C}{C}}$$

$$\dfrac{\mathrm d f(x)}{\sqrt{[f(x)]^2 - C}}=\dfrac{\mathrm d x}{\sqrt{C}}$$

## 题面翻译

### 大意

1. 所有点的坐标均为整数且 $-10^{9} \leqslant x,y \leqslant 10^{9}$ 。
2. 对于该凸多边形的任意内角 $\alpha$ ，均有 $90^{\circ} \leqslant \alpha < 180^{\circ}$ 。

## 正文

### 大致所需知识

• 曲线上点坐标的参数方程表示。
• 函数图像变换。
• 三角函数积化和差与和差化积公式。
• 定积分。
• 二分求根。

### 程序构建脉络

\begin{aligned} &\Rightarrow x_\text{I}=\dfrac{\sin(\theta+\alpha)}{\sin\alpha},y_\text{J}=\dfrac{\sin(\theta+\alpha)}{ \sin\alpha}\tan\theta \\& \therefore \ l_\text{HI}:\dfrac{\sin\alpha \cdot x}{\sin(\theta+\alpha)}+\dfrac{\sin\alpha \cdot y}{\tan\theta\sin(\theta+\alpha)}=1 \end{aligned}

\begin{aligned}&\dfrac{x_\text{I}}{\sin(\theta-\alpha)}=\dfrac{1}{\sin\alpha},y_\text{J}=-\tan\theta \cdot x_\text{I}\\ \\ \Rightarrow & x_\text{I}=\dfrac{\sin(\theta-\alpha)}{\sin\alpha} , y_\text{J}=-\dfrac{\sin(\theta-\alpha)}{\sin\alpha}\tan\theta \\ \\l:&\dfrac{x(\theta,\alpha)}{x_\text{I}}+\dfrac{y(\theta,\alpha)}{y_\text{J}}=1,\ \dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{y_\theta}{x_\theta}=\tan\theta \\ \Rightarrow & -\tan\theta\cdot x(\theta,\alpha)+y(\theta,\alpha)=-\dfrac{\sin(\theta-\alpha)}{\sin\alpha}\tan\theta ,\ y_\theta=\tan\theta \cdot x_\theta \\ \therefore &-\dfrac{x(\theta,\alpha)}{\cos^2\theta}-x_\theta\tan\theta+y_\theta=\csc\alpha(-\cos(\theta-\alpha)\tan\theta-\sin(\theta-\alpha)\sec^2\theta)\\ \\\Rightarrow &-\dfrac{x(\theta,\alpha)}{\cos^2\theta}= -\dfrac{\sin(\theta-\alpha)+\sin\theta\cos\theta\cos(\theta-\alpha)}{\sin\alpha\cos^2\theta} \\\Rightarrow &x(\theta,\alpha)=\dfrac{\sin(\theta-\alpha)+\sin\theta\cos\theta\cos(\theta-\alpha)}{\sin\alpha},y(\theta,\alpha)=\dfrac{\sin^2\theta\cos(\theta-\alpha)}{\sin\alpha} \end{aligned}

\begin{aligned} x_\theta&=\csc\alpha[\cos(\theta-\alpha)+\cos2\theta\cos(\theta-\alpha)-\dfrac{1}{2}\sin2\theta\sin(\theta-\alpha)] \\ \therefore \text{S}&=\int_\alpha^\pi y(\theta,\alpha)\cdot x_\theta\mathrm{d}\theta \\ \Rightarrow \text{S}&=\csc^2\alpha\int_\alpha^\pi\sin^2\theta\cos(\theta-\alpha)[(1+\cos2\theta)\cos(\theta-\alpha)-\dfrac{1}{2}\sin2\theta\sin(\theta-\alpha)]\mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{4}\int_\alpha^\pi 8\cos^2\theta\sin^2\theta\cos^2(\theta-\alpha)-\sin^2\theta\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{4}\int_\alpha^\pi 2\sin^22\theta\cos^2(\theta-\alpha)-\sin^2\theta\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{4}\int_\alpha^\pi \sin^22\theta+\sin^22\theta\cos(2\theta-2\alpha)-\sin^2\theta\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{8}\int_\alpha^\pi 1-\cos4\theta+ (1-\cos4\theta)\cos(2\theta-2\alpha)-(1-\cos2\theta)\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{16}\int_\alpha^\pi 2-2\cos4\theta+ 2\cos(2\theta-2\alpha)-2\cos4\theta\cos(2\theta-2\alpha) -(1-\cos2\theta)(\cos(-2\alpha)-\cos(4\theta-2\alpha)) \mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{16}\int_\alpha^\pi 2-2\cos4\theta+ 2\cos(2\theta-2\alpha)-\cos(6\theta-2\alpha)-\cos (2\alpha+2\theta) -\cos2\alpha+\cos(4\theta-2\alpha) +\cos2\theta\cos2\alpha-\cos2\theta\cos(4\theta-2\alpha) \mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{32}\int_\alpha^\pi 4-4\cos4\theta+ 4\cos(2\theta-2\alpha)-2\cos(6\theta-2\alpha)-2\cos (2\alpha+2\theta) -2\cos2\alpha+2\cos(4\theta-2\alpha) +2\cos2\alpha\cos2\theta-\cos(6\theta-2\alpha)-\cos(2\theta-2\alpha) \mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{32}\int_\alpha^\pi 4-4\cos4\theta+ 4\cos(2\theta-2\alpha)-3\cos(6\theta-2\alpha)-\cos (2\alpha+2\theta) -2\cos2\alpha+2\cos(4\theta-2\alpha) \mathrm{d}\theta \\&= \dfrac{\csc^2\alpha}{64}\int_\alpha^\pi 8-8\cos4\theta+ 8\cos(2\theta-2\alpha)-6\cos(6\theta-2\alpha)-2\cos (2\alpha+2\theta) -4\cos2\alpha+4\cos(4\theta-2\alpha) \mathrm{d}\theta \\ \Rightarrow \text{S}&=\left. \dfrac{\csc^2\alpha}{64}(8\theta-2\sin4\theta+4\sin(2\theta-2\alpha)-\sin(6\theta-2\alpha)-\sin(2\theta+2\alpha) -4\cos2\alpha\cdot\theta+\sin(4\theta-2\alpha))\right|_{\alpha}^{\pi} \end{aligned}

1. 对于不包含交点的面积，需要再加上 $\dfrac{1}{2}\sin\alpha\cos\alpha$。
2. 对于含有交点的部分，只需换 $\alpha$ 为二分套二分求得的 $\theta_i$ 即可。

$$-\tan\theta=\dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{\mathrm{d}y(\theta,\alpha)}{\mathrm{d}x(\theta,\alpha)}$$

$$-\tan\theta=\dfrac{y_\theta}{x_\theta}\Rightarrow y_\theta=-\tan\theta \cdot x_\theta$$

$$\left\{\begin{matrix} \dfrac{\sin\alpha \cdot x(\theta,\alpha)}{\sin(\theta+\alpha)}+\dfrac{\sin\alpha \cdot y(\theta,\alpha)}{\tan\theta\sin(\theta+\alpha)}=1 \\ \\ y_\theta=-\tan\theta \cdot x_\theta \end{matrix}\right.$$

\begin{aligned} &\tan\theta \cdot x(\theta,\alpha)+y(\theta,\alpha)=\dfrac{\tan\theta\sin(\theta+\alpha)}{\sin\alpha} \\&\Rightarrow \dfrac{x(\theta,\alpha)}{\cos^2\theta}+\tan\theta \cdot x_\theta+y_\theta=\frac{\tan\theta\cos(\theta+\alpha)}{\sin\alpha}+\dfrac{\sin(\theta+\alpha)}{\sin\alpha\cos^2\theta} \\&\Rightarrow x(\theta,\alpha)+\overbrace{\tan\theta \cdot x_\theta+y_\theta}^0=\dfrac{\sin(\theta+\alpha)+\sin\theta \cos\theta \cos(\theta+\alpha)}{\sin\alpha} \\&\Rightarrow y(\theta,\alpha)=\dfrac{\tan\theta\sin(\theta+\alpha)}{\sin\alpha}-\dfrac{\tan\theta\sin(\theta+\alpha)+\sin^2\theta\cos(\theta+\alpha)}{\sin\alpha} \\ \\ & \therefore \left\{\begin{matrix} \begin{aligned} &x(\theta,\alpha)=\dfrac{\sin2\theta\cdot \cos(\theta+\alpha)+2\sin(\theta+\alpha)}{2\sin\alpha} \\&y(\theta,\alpha)= -\dfrac{\sin^2\theta\cdot \cos(\theta+\alpha)}{\sin\alpha} \end{aligned} \end{matrix}\right. \end{aligned}

$$\text{S}=\int y(t_1,t_2,\ldots,t_n)\mathrm{d}[x(t_1,t_2,\ldots,t_n)]$$

$$\text{S}=\int y(\theta,\alpha)\mathrm{d}[x(\theta,\alpha)]=\int y(\theta,\alpha)\frac{\partial x(\theta,\alpha)}{\partial\theta}\mathrm{d}\theta$$

$$\text{S}=\int^{0}_{\pi-\alpha} y(\theta,\alpha)\frac{\partial x(\theta,\alpha)}{\partial\theta}\mathrm{d}\theta$$

\begin{aligned} \text{S}&=\left. \dfrac{1}{64\sin^2\alpha} [ (8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha) -\sin(6\theta+2\alpha) +\sin(2\alpha-2\theta) +\sin(4\theta+2\alpha)] \right|_{0}^{\pi-\alpha} \end{aligned}

\begin{aligned} \text{S}&=\int_{\pi-\alpha}^{0}y(\theta,\alpha)\mathrm{d}[x(\theta,\alpha)] \\ &=\int_{0}^{\pi-\alpha}\dfrac{\sin^2\theta\cdot \cos(\theta+\alpha)}{\sin\alpha}\mathrm{d}[\dfrac{\sin2\theta\cdot \cos(\theta+\alpha)+2\sin(\theta+\alpha)}{2\sin\alpha}] \\ &=\dfrac{1}{2\sin^2\alpha}\int_{0}^{\pi-\alpha} \sin^2\theta\cdot \cos[\theta+\alpha](2\cos2\theta\cdot\cos(\theta+\alpha)-\sin2\theta\cdot\sin(\theta+\alpha)+2\cos(\theta+\alpha))\mathrm{d\theta} \\ &=\dfrac{1}{2\sin^2\alpha} \int_{0}^{\pi-\alpha} \sin^2\theta [2\cos^2(\theta+\alpha)(1+\cos2\theta) -\sin2\theta\sin(\theta+\alpha)\cos(\theta+\alpha)] \mathrm{d\theta} \\ &=\dfrac{1}{4\sin^2\alpha} \int_{0}^{\pi-\alpha} (1-\cos2\theta) [(1+\cos(2\theta+2\alpha))(1+\cos2\theta) -\sin2\theta\sin(\theta+\alpha)\cos(\theta+\alpha)] \mathrm{d\theta} \\ &=\dfrac{1}{4\sin^2\alpha} \int_{0}^{\pi-\alpha} (1+\cos(2\theta+2\alpha))(1-\cos^22\theta) -\sin2\theta\sin(\theta+\alpha)\cos(\theta+\alpha) +\sin2\theta\cos2\theta\sin(\theta+\alpha)\cos(\theta+\alpha) \mathrm{d\theta} \\ &=\dfrac{1}{16\sin^2\alpha} \int_{0}^{\pi-\alpha} 2(1+\cos(2\theta+2\alpha))(1-\cos4\theta) -2\sin2\theta\sin(2\theta+2\alpha) +\sin4\theta\sin(2\theta+2\alpha) \mathrm{d\theta} \\ &=\dfrac{1}{16\sin^2\alpha} \int_{0}^{\pi-\alpha} 2-2\cos4\theta+2\cos(2\theta+2\alpha)-2\cos(2\theta+2\alpha)\cos4\theta -\cos2\alpha+\cos(4\theta+2\alpha) +\dfrac{1}{2}\cos(2\alpha-2\theta)-\dfrac{1}{2}\cos(2\alpha+6\theta) \mathrm{d\theta} \\ &=\dfrac{1}{32\sin^2\alpha} \int_{0}^{\pi-\alpha} 4-4\cos4\theta+4\cos(2\theta+2\alpha) -2\cos(6\theta+2\alpha)-2\cos(2\alpha-2\theta) -2\cos2\alpha+2\cos(4\theta+2\alpha) +\cos(2\alpha-2\theta)-\cos(2\alpha+6\theta) \mathrm{d\theta} \\ &=\dfrac{1}{32\sin^2\alpha} \int_{0}^{\pi-\alpha} 4-4\cos4\theta+4\cos(2\theta+2\alpha) -3\cos(6\theta+2\alpha)-\cos(2\alpha-2\theta) -2\cos2\alpha+2\cos(4\theta+2\alpha) \mathrm{d\theta} \\ &=\left. \dfrac{1}{32\sin^2\alpha} [ 4\theta-\sin4\theta+2\sin(2\theta+2\alpha)-\dfrac{1}{2}\sin(6\theta+2\alpha)+\dfrac{1}{2}\sin(2\alpha-2\theta) -2\cos2\alpha\cdot\theta+\dfrac{1}{2}\sin(4\theta+2\alpha)] \right|_ {0}^{\pi-\alpha} \\ &=\left. \dfrac{1}{64\sin^2\alpha} [ (8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha) -\sin(6\theta+2\alpha) +\sin(2\alpha-2\theta) +\sin(4\theta+2\alpha)] \right|_{0}^{\pi-\alpha} \end{aligned}

\begin{aligned} \text{S}&=\left. \dfrac{1}{64\sin^2\alpha} [ (8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha) -\sin(6\theta+2\alpha) +\sin(2\alpha-2\theta) +\sin(4\theta+2\alpha)] \right|_{0}^{\theta_{u,i}} \end{aligned}

### 代码实现

C++ 代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
using db = long double;
const int N = 5001;
const db eps = 1e-6, pi = acos((db)-1);

class vec{
public:
ll x, y;
vec(ll xx = 0, ll yy = 0) : x(xx), y(yy) {}
vec(const vec &a) : x(a.x), y(a.y) {}
vec operator-(const vec &a) const { return vec(x - a.x, y - a.y); }
db len() { return (db)sqrt(x * x + y * y); }
vec rev() { return vec(-x, -y); }
} dot[N], edge[N];

inline db angle(vec a, vec b) {return acos(a.x * b.x / a.len() / b.len()
+ a.y * b.y / a.len() / b.len());}
// atan2(a.x * b.y - a.y * b.x, a.x * b.x + a.y * b.y)

inline db interg(db theta, db alpha){ // 上下界代入式
return ((8.0 - 4.0 * cos(2.0 * alpha)) * theta - 2.0 * sin(4 * theta) + 4.0 * sin(2.0 * (theta + alpha))
- sin(2.0 * (8.0 * theta + alpha)) + sin(2.0 * (alpha - theta)) + sin(2.0 * (2.0 * theta + 3.0 * alpha)))
/ sin(alpha) / sin(alpha) / 64.0;
}

inline db overlap(db mida, db midb, db ang1, db ang2){return interg(midb, ang1) + interg(mida, ang2)
- interg(0, ang1) - interg(0, ang2);}

void calc(db &h, db &l, db ang, db Y){ // 求两条曲线交点的参数theta
while (fabs(h - l) > eps){
db mid = h / 2.0 + l / 2.0;
db yy = -pow(sin(mid), 2) / sin(ang) * cos(mid + ang);
if (yy < Y) h = mid;
if (yy > Y) l = mid;
}
return;
}
db getarea(int _n, int n, int nt){
auto now = edge[n], lst = edge[_n], nxt = edge[nt];
db res = 0.0, len = now.len(),
alpha1 = angle(now, lst.rev()), alpha2 = angle(nxt, now.rev());
if (len < 2.0){
db la = 0.0, lb = 0.0,
ra = pi - alpha1, rb = pi - alpha2,
cy = sin(min(alpha1, alpha2)), fy = 0, mida, midb;

while (fabs(cy - fy) > eps){   // 二分套二分
db midy = cy / 2.0 + fy / 2.0;
la = 0.0, lb = 0.0, ra = pi - alpha1, rb = pi - alpha2;
calc(ra, la, alpha1, midy), calc(rb, lb, alpha2, midy);

mida = la / 2.0 + ra / 2.0, midb = lb / 2.0 + rb / 2.0;
db x1 = (sin(2.0 * mida) * cos(alpha1 + mida) + 2 * sin(mida + alpha1)) / 2.0 / sin(alpha1),
x2 = len - (sin(2.0 * midb) * cos(alpha2 + midb) + 2 * sin(midb + alpha2)) / 2.0 / sin(alpha2);

if (x1 < x2) cy = midy;
if (x1 > x2) fy = midy;
}

res -= overlap(mida, midb, alpha1, alpha2);
}
res += interg(pi - alpha1, alpha1) - interg(0, alpha1) + 0.25 * sin(alpha1) * cos(alpha1);
// 推荐积分求解，不推荐写成 3*(pi-alpha)/16 + 1/16/tan(alpha) + (pi-alpha)/16/tan(alpha)/tan(alpha)
return res;
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%ld %ld", &dot[i].x, &dot[i].y);
for (int i = 0; i < n; ++i)
edge[i] = vec(dot[(i + 1) % n] - dot[i]);
if (n == 4){                    // 特判4个点时的情况
db len1 = edge[0].len(), len2 = edge[1].len(),
len3 = edge[2].len(), len4 = edge[3].len();

if (len1 == len3 and len2 == len4 and
(len1 == 1 or len2 == 1) and
fabs(angle(edge[0], edge[1]) - pi / 2.0) < eps)
printf("%.11lf", len1 * len2), exit(0);
}
db res = 0.0;
for (int i = 0; i < n; ++i)
res += getarea((i - 1 + n) % n, i, (i + 1) % n);
printf("%.11lf", res);
return 0;
}


Python 3 的代码。

import math
pi = 3.14159265358979323846264338327950288419716939937510
eps, sq2 = 1e-6, pow(2, 0.5)
x, y, n = [], [], 0

def fabs(xx):
return math.fabs(xx)

def Sin(xx):
return math.sin(xx)

def Cos(xx):
return math.cos(xx)

def Acos(xx):
return math.acos(xx)

def get_len(ux, uy):
return pow((pow(ux, 2) + pow(uy, 2)), 0.5)

def angel_(ux, uy, vx, vy, u, v):
return Acos((ux * vx + uy * vy) / u / v)

def small(_a: float, _b: float) -> bool:
return fabs(_a - _b) < eps

def big(_a: float, _b: float) -> bool:
return fabs(_a - _b) > eps

def inter_grate(theta, alpha):
ans = ((8 - 4 * Cos(2 * alpha)) * theta - 2 * Sin(4 * theta) + 4 * Sin(2 * theta + 2 * alpha)
- Sin(6 * theta + 2 * alpha) + Sin(2 * alpha - 2 * theta)
+ Sin(4 * theta + 2 * alpha)) / (64 * pow(Sin(alpha), 2))
return ans

def calc(la, ra, mid_y, alpha_1):
while big(ra, la):
mid_a = ra / 2.0 + la / 2.0
yy = - pow(Sin(mid_a), 2) / Sin(alpha_1) * Cos(alpha_1 + mid_a)
if yy > mid_y:
la = mid_a
if yy < mid_y:
ra = mid_a
return la, ra

def formulas_x(la, ra, alpha_1):
return (2.0 * Sin(la / 2.0 + ra / 2.0 + alpha_1) + Sin(la + ra)
* Cos(la / 2.0 + ra / 2.0 + alpha_1)) / (2 * Sin(alpha_1))

def binary_find(la, lb, ra, rb, cy, fy, alpha_1, alpha_2, ab):
while big(cy, fy):
mid_y = cy / 2.0 + fy / 2.0
la, lb, ra, rb = 0.0, 0.0, pi - alpha_1, pi - alpha_2

la, ra = calc(la, ra, mid_y, alpha_1)
lb, rb = calc(lb, rb, mid_y, alpha_2)

x1, x2 = formulas_x(la, ra, alpha_1), ab - formulas_x(lb, rb, alpha_2)

if x1 < x2:
cy = mid_y
if x1 > x2:
fy = mid_y
return la, lb, ra, rb, cy, fy

def get_area(_i, ni, i_, i_2):
ans = 0.00
ux, uy, vx, vy = x[_i] - x[ni], y[_i] - y[ni], x[i_] - x[ni], y[i_] - y[ni]

ab, ad = get_len(ux, vy), get_len(vx, uy)
alpha_1 = angel_(ux, vy, vx, uy, ab, ad)

if small(ab, sq2) or small(ab, 1.00):
wx, wy = x[i_2] - x[i_], y[i_2] - y[i_]

bc = get_len(wx, wy)
alpha_2 = angel_(wx, wy, vx, vy, ab, bc)

la, lb, ra, rb, cy, fy = 0.0, 0.0, pi - alpha_1, pi - alpha_2, Sin(min(alpha_1, alpha_2)), 0.0000
la, lb, ra, rb, cy, fy = binary_find(la, lb, ra, rb, cy, fy, alpha_1, alpha_2, ab)

ans -= inter_grate(la / 2.0 + ra / 2.0, alpha_1) - inter_grate(0, alpha_1)
ans -= inter_grate(lb / 2.0 + rb / 2.0, alpha_2) - inter_grate(0, alpha_2)

ans += inter_grate(pi - alpha_1, alpha_1) - inter_grate(0, alpha_1) + 0.5 * Sin(alpha_1) * Cos(alpha_1)
return ans

if __name__ == "__main__":
n = eval(input())
for i in range(1, n + 1):
a, b = input().split()
a, b = int(eval(a)), int(eval(b))
x.append(a), y.append(b)
if n == 4:
Ax, Ay, Bx, By, Cx, Cy, Dx, Dy = x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]
ABx, ABy, ADx, ADy = Bx - Ax, By - Ay, Dx - Ax, Dy - Ay
CBx, CBy, CDx, CDy = Bx - Cx, By - Cy, Dx - Cx, Dy - Cy

if small(a, pi / 2.0) and small(b, pi / 2.0) and small(c, pi / 2.0) and small(d, pi / 2.0) and \
((small(LenAB, 1.00) and small(LenAB, LenCD)) or (small(LenCB, 1.00) and small(LenCB, LenAD))):
print('%.11Lf' % (LenAB * LenCB)), exit(0)

res = 0.0000
for i in range(1, n + 1):
res += get_area((i - 1 + n) % n, i % n, (i + 1) % n, (i + 2) % n)

print('%.11Lf' % res)



### 问题拓展

\begin{aligned}&\dfrac{x_0}{\sin(\pi-\alpha-\theta)} = \dfrac{1}{\sin\alpha}\Rightarrow x_0 = \dfrac{\sin(\alpha+\theta)}{\sin\alpha} \\ &\dfrac{\mathrm d y}{\mathrm d x} = \dfrac{y_\theta}{x_\theta} = -\tan\theta\Rightarrow y_\theta = -\tan\theta x_\theta\end{aligned}

$$\begin{cases}x = \dfrac{2\sin(\alpha + \theta) + \sin2\theta\cos(\alpha + \theta)}{2\sin\alpha} \\ y = -\dfrac{\sin^2\theta\cos(\alpha + \theta)}{2\sin\alpha} \end{cases}$$

\begin{aligned}\text{S}(\alpha) &= \dfrac{1}{2\tan\alpha} + \Big(\left. \dfrac{1}{64\sin^2\alpha} [ (8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha) -\sin(6\theta+2\alpha) +\sin(2\alpha-2\theta) +\sin(4\theta+2\alpha)] \right|_{\frac{\pi}{2} - \alpha}^{\frac{\pi}{2}}\Big). \end{aligned}

### 参考网页与在线工具

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 5E4 + 10,
M = 2E5 + 10,
S = 1E6 + 10;
int n, m, len = 1,
a[N], res[M];

int cnt[S];                         // 用于计数用

inline int get(int i) {return i / len;}
inline void add(int x, int &ans) {if(++cnt[x] == 1) ans ++;}
inline void sub(int x, int &ans) {if(!--cnt[x])     ans --;}

struct node {int id, l , r;}q[M];

int main() {

scanf("%d", &n);
for(int _ = 1; _ <= n; ++_)
scanf("%d", a + _);
scanf("%d", &m);

len = max(1, (int)sqrtf((double)n * n / m));
int l, r;
for(int i = 0; i < m; ++i)
{
scanf("%d %d", &l, &r);
q[i] = {i, l, r};
}

sort(q, q + m, [&](node &a, node &b) {
int al = get(a.l), bl = get(b.l);
if(al ^ bl) return al < bl;
return a.r > b.r;
});                             // 横跨整段的优先

for(int k = 0, i = 1, j = 0, ans = 0; k < m; ++k)
{
int id = q[k].id, l = q[k].l, r = q[k].r;

while(j > r) sub(a[j--], ans);
while(i < l) sub(a[i++], ans);

res[id] = ans;
}
for(int _ = 0; _ < m; ++_)
printf("%d\n", res[_]);
return 0;
}