发表更新解题报告

2011 ACM-ICPC World Finals 解题报告

WF 不愧是 WF，眼高手低人被打成粉末。

[TOC]

A

有两种操作：

  • $A$ 操作：将当前数加 $a$

  • $M$ 操作：将当前数乘 $m$

给出 $a,m$ ，构造一个操作序列，将 $[p,q]$ 中的每个数变换为 $[r,s]$ 中的一个数。在此基础上最小化长度，在此基础上最小化字典序。

$a,m,p,q,r,s\leq 10^9$。

显然的观察是，$M$ 操作是 $\log$ 级别的了。

那么你考虑 $[p,q]$ 里面如果我们能把 $p$ 给转化到 $[r,s]$，则必定可以利用某个操作序列转化其他的到 $[r,s]$ 里面。

这是本题第一个关键点，第二个关键点是，我们怎么处理 $A$ 操作？

观察可得，我们可以把最终的 $p$ 表示为 $p=a\times (m^{P_1}+ m^{P_2}+\dots +m^{P_n})$ 的形式，这样实际上是构造了一个 $m$ 进制的数，所以我们要确定的也就是 $P_1\dots P_n$。

首先我们需要保证 $n$ 最小，也就是这个数每位上的数字和最小。从高位枚举下来，贪心处理。时间复杂度不太会算，但是能过。

思考题

有一个不知道次数的 $f(x) = \sum_{k=0}^n a_kx^k(a_i\in \N)$,用最小次数将每个 $a_i$ 求出来。

和上面一样的思路，其实只要两次就能求出来了。第一次求出来 $f(1) = \sum_{k = 0}^n a_k$,算 $f(f(1))$ 实际上就表示出来一个 $f(1)$ 进制的数。

C

有六种远古符号如图所示：

image-20210701232824437

给出一张像素图，判断图中写的是哪种符号。

$n,m\leq 200$

这个题观察到直接搜轮廓其实是很不好搜的，转化一下问题，与其搜黑色的连通块不如搜白色的连通块。

这边就需要一点观察了，这六个图形中完全包含的白色部分分别有 1，3，5，4，0，2 个，于是你做一下搜索就写完了，实际上可能并没有那么好写

E

平面上有 $n$ 个咖啡店，$q$ 次询问，每次询问如下：

找一个点，距离其曼哈顿距离不超过 $m$ 的咖啡店最多。

$n\leq 500000,q\leq 20$,坐标范围 $[1,1000]$。

注意到这个题其实没有那么简单，因为这个形成的图由若干个翻转 $45$ ° 的矩形组成， 大致是这样的。

image-20210701234615822

斜的图我们实际上非常讨厌，因为没有办法很快计算。

所以我们采用一个将曼哈顿距离转化为切比雪夫距离的方法，将整张图变成若干个矩形的经典样式，然后发现坐标范围只有 $[0,1000]$ 直接大力选出交集最多的矩形即可。

时间复杂度 $O(nm)$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define ri int
#define int long long

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	ri v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const int N = 5e5 + 10;

struct poi {
    int x,y;
}p[N];

int dx,dy,n,m,sum[2010][2010],ma[2010][2010];

void solve(int qwq) {
    int ans = 0,posx,posy;
     for (int j = 1;j <= dy;++j) {
        for (int i = 1;i <= dx;++i){
            int x = i + j - 1,y = i-j + dy;
            int x1 = max(1ll,x - qwq),x2 = min(dx + dy - 1,x + qwq );
            int y1 = max(1ll,y - qwq),y2 = min(dx + dy - 1,y + qwq);
            if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1 - 1][y1 - 1] > ans) {
                ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1 - 1][y1 - 1];
                posx = i,posy = j;
            } else if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1 - 1][y1 - 1] == ans) {
                if (posy > j) {
                    posx = i,posy = j;
                } else if (posy == j && posx > i) {
                    posx = i,posy = j;

                }
            }
        }
    }
    printf("%lld (%lld,%lld)\n",ans,posx,posy);
}

signed main() {
    int $ = 0;
	while (1) {
        memset(ma,0,sizeof ma);
        memset(sum,0,sizeof sum);
        read(dx,dy,n,m);
        if (dx == 0 && dy == 0 && n == 0 && m == 0) return 0;
        printf("Case %d:\n",++$);
        for (int i = 1;i <= n;++i) {
            int x,y;read(x,y);
            p[i].x = x+y-1,p[i].y = x-y+dy;
            //printf("%d %d\n",p[i].x,p[i].y);
            ma[p[i].x][p[i].y]=1;
        }
        for (int i = 1;i <= dx + dy - 1;++i) {
            for (int j = 1;j <= dx + dy - 1;++j) {
                sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + ma[i][j];
                //printf("%d ",sum[i][j]);
            }
            //puts("");
        }
        while (m--) {
            int x;read(x);
            solve(x);
        }
    }
	return 0;
}

F

若干台机器，你可以在 $d_i$ 天以 $p_i$ 的价格买入第 $i$ 台机器（钱不够买不了），在下一天开始运行它，每天产生 $g_i$ 利润，并且可以选择随时将其卖出去得到 $r_i$元。

初始你有 $c$ 元，一共有 $d$ 天，结束时卖出所有机器。求最多能获得多少利润。

$n\leq 10^5$

$$
f_i= \max_{1\leq j < i}{f_j + g_i * (d_i - d_j) + r_j - p_i}(r_j - p_i + now \geq 0)\
$$

斜率优化，CDQ分治维护凸壳

没有 code 因为我不会写

G

给出若干根首尾相接的火柴。

允许将其拆分后围成多边形，最大化围成的面积。

$n\leq 500$

没有 code 因为我不会写

H

有 $n$ 个矿井，由 $m$ 个隧道连接。

现在要在某些矿井安装逃生通道，使得任何一个矿井发生坍塌的时候，其余矿井的人都能逃到地面。

求最小的通道数量，以及最优方案数。

$n,m\leq 5\times 10^4$

经典题。

首先我们考虑割点被炸掉的情况，似乎我们只需要在每个点双连通分量里面做一个通道数就可以了。

但是如下这个图可以 hack 掉这个做法

image-20210701235848922

蓝色为割点，黑色为点双联通分量。

那么因为只炸掉一个点，所以两个割点任意炸掉一个另外两个点双都是可以互相到达的，只要建一个就行。

所以我们注意到，如果一个点双里面只存在一个割点，那么必须在这个点双加上一个通道，否则就不用。

注意特判掉只有一个点双（一个环） 的情况。

这里我们可以引出一个数据结构：圆方树。

众所周知边双是可以直接把桥当成树边缩点为一棵树的，但是点双由于会产生一个割点在多个点双里的情况，所以不能直接缩点。

我们考虑把所有割点提出来，往它所在的所有点双连边，点双之间连边，这样就形成了一颗树。

这棵树我们叫其圆方树，一张著名的图可以阐述名字来源。

那么这个题就变成了圆方树叶子节点个数。

时间复杂度 $O(n)$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define ri int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	ri v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const int N = 5e4 + 10;

ll T,m,n,dfn[N],low[N],cnt,num,s[N],top,c,nn,bcc[N];
ll ans1,ans2;
bool cut[N];

vector <int> G[N];

void init() {
    ans1 = 0; ans2 = 1;
    for (int i = 1;i < N;++i) {
        G[i].clear();cnt = 0;
        dfn[i] = 0;cut[i] = 0;low[i] = 0;bcc[i] =  0;
    }
}

void tarjan(int x,int anc) {
    dfn[x] = low[x] = ++cnt;
    int isroot = 0;
    for (auto y : G[x]) {
        if (!dfn[y]) {
            tarjan(y,anc);
            low[x] = min(low[x],low[y]);
            if (low[y] >= dfn[x]) {
                ++isroot;
                if (x != anc || isroot > 1) {
                    cut[x] = 1;
                }
            }
        } else {
            low[x] = min(low[x],dfn[y]);
        }
    }
}

void dfs(int x,int col) {
    bcc[x] = col;++nn;
    for (auto y : G[x]) {
        if (cut[y] && bcc[y] != col) {
            ++c;
            bcc[y] = col;
        }
        if (!bcc[y]) {
            dfs(y,col);
        }
    }
}

void solve() {
    printf("Case %d: ",++T);
    n = 0;
    init();
    for (int i =1;i <= m;++i) {
        ll x,y;read(x,y);
        n = max(n,x);n = max(n,y);
        G[x].push_back(y),G[y].push_back(x);
    }
    for (int i = 1;i <= n;++i) {
        if (!dfn[i]) s[top=1] = i,tarjan(i,i);
    }
    //printf("%d\n",n);
    for (int i = 1;i <= n;++i) {
        if (!bcc[i] && !cut[i]) {
            c = nn = 0;
            dfs(i,++num);
            if (c == 1) ++ans1,ans2 *= nn;
            else if (!c) ans1 += 2,ans2 *= (nn-1)*nn/2;
        }
    }


/*
    for (int i = 1;i <= num;++i) {
        int tot = 0;
        for (auto x:bcc[i]) {
            tot += cut[x];
        }
        if (tot == 1) ++ans1,ans2 += bcc[i].size() * (bcc[i].size() - 1) / 2;
        if (!tot) ++ans1,ans2 += bcc[i].size();
    } */
    printf("%lld %lld\n",ans1,ans2);
}

signed main() {
	while (1) {
        read(m);
        if (m) solve();
        else break;
    }
	return 0;
}

J

有 $c$ 块砖，你可以摆出两种类型的金字塔：

$n\times n，(n-1)\times(n-1)，…$

$n\times n，(n-2)\times (n-2)，…$

你需要恰好用完这些砖，最小化堆成的金字塔的数量，在此基础上最大化最大金字塔，在此基础上最大化第二大的金字塔，……

$c \leq 10^6$，Time Limit:10s

诈骗题。

我们考虑将第一个式子化一下 $\sum_{i=0}^{n-1} (n-i)^2 = \frac{n\times(n+1)\times(2n+1)}{6}$

所以我们可以搭的金字塔个数在 $O(n^{\frac{1}{3}})$ 级别的，大约是 $300$

所以直接跑一个 01 背包即可，时间复杂度 $O(ct)$，t为物品数，注意是 10 秒，所以能过。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define ri int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	ri v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const int N = 1e6+10;
const int K = 330;

int f[N],n;
bool road[N][K];

struct node {
    int v,w,typ,num;
    friend inline bool operator < (node a,node b) {
        return a.v < b.v;
    }
}a[K];

signed main() {
    //freopen("fuck.txt","w",stdout);
    //freopen("qwq.txt","r",stdin);
    int $ = 0;
    int tot = 0,cnt = 2;
    n = 1000000;
    for (int i = 2,sum = 1;sum <= n;i ++) {
        //printf("%d\n",sum);
        sum += i * i;
        a[++tot].v = sum;a[tot].typ = 1;a[tot].num = i;
    }
    for (int i = 3,sum = 1;sum <= n;i += 2) {
        //printf("%d\n",sum);
        sum += i * i;
        a[++tot].v = sum;a[tot].typ = 2;a[tot].num = i;
    }
    for (int i = 4,sum = 4;sum <= n;i += 2) {
        sum += i * i;
        a[++tot].v = sum;a[tot].typ = 2;a[tot].num = i;
        //printf("%d\n",sum);
    }
    //puts("here");
    //printf("%d\n",tot);
    sort(a+1,a+1+tot);
    memset(f,0x3f,sizeof f);
    f[0] = 0;
    int qwq = 0;
    for (int i = 1;i <= tot;++i) {
        qwq += a[i].v;
        //printf("%d ",qwq);
        if (qwq > 1000000) qwq = 1000000;
        for (int j = qwq;j >= a[i].v;--j) {
            //printf("%d ",j);
            if (f[j-a[i].v]+1 <= f[j]) {
                road[j][i] = 1;
                f[j] = min(f[j],f[j-a[i].v] + 1);
            }
            //printf("%d %d\n",i,j);
        }
    }
    //for (int i = tot-10;i <= tot;++i) printf("%d %d %d\n",a[i].v,a[i].typ,a[i].num);
    while (~scanf("%d",&n)){
        if (n == 0) break;
        printf("Case %d: ",++$);
        
        //cout << f[n] << endl;
        if (f[n] == 0x3f3f3f3f) {
            puts("impossible");
            continue;
        }
        int now = n;
        //while (now){
        for (int i = tot;i;--i) {
            if (road[now][i]) {
                printf("%d",a[i].num);
                if (a[i].typ == 1) putchar('H');
                else putchar('L');
                now -= a[i].v;
                putchar(' ');
            }
        }
        //}
        puts("");

    }
	return 0;
}

I

平面上有 $n$ 个木乃伊在追你

在你的回合，你能朝上下左右走一步。

在木乃伊的回合，他们会朝着离你最近的坐标轴方向走一步。

求最多可以支撑几个回合，或是可以逃走。

$n\leq 100000$

首先让你求最多，我们考虑这个可以支撑的回合显然是有单调性的，考虑二分。

我们接着考虑如何 check，假设当前在 $m$ 回合，我们显然可以把木乃伊追到人的范围画成一个矩形，再把我自己画一个矩形，如图

image-20210702001600372

如果我所在的红色矩形没有被完全包含，那么我就是有一丝生机的，反之活不下去。

所以我们利用扫描线先算一下面积并，然后加进去红色矩形再算一次面积并，看一下两个面积并是否有差，如果没有说明死亡。

时间复杂度 $O(n\log n)$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define ri int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    ri v = getchar();
    T f = 1;
    t = 0;

    while (!isdigit(v)) {
        if (v == '-')
            f = -1;

        v = getchar();
    }

    while (isdigit(v)) {
        t = t * 10 + v - 48;
        v = getchar();
    }

    t *= f;
}
template <typename T, typename... Args> inline void read(T &t, Args &... args) {
    read(t);
    read(args...);
}

const int N = 1e5 + 10;
const int M = 2e6 + 10;
const int delta = 1e6 + 1;

int n,kas,js,SZ,rt;
struct mummy {
    int x, y;
} mu[N];
struct line {
    int x, l, r, op;
} seg[N << 1];
struct node {
    int ls, rs;
    ll v, lz;
} tr[N * 40];

bool cmp(line l1, line l2) {
    return l1.x < l2.x;
}
void up(int x, int s, int t) {
    if (tr[x].lz)
        tr[x].v = t - s + 1;
    else if (s == t)
        tr[x].v = 0;
    else
        tr[x].v = tr[tr[x].ls].v + tr[tr[x].rs].v;
}
void ins(int l, int r, int s, int t, int &x, ll num) {
    if (!x)
        x = ++SZ, tr[x].v = tr[x].lz = tr[x].ls = tr[x].rs = 0;

    if (l <= s && t <= r) {
        tr[x].lz += num, up(x, s, t);
        return;
    }

    int mid = (s + t) >> 1;

    if (l <= mid)
        ins(l, r, s, mid, tr[x].ls, num);

    if (mid + 1 <= r)
        ins(l, r, mid + 1, t, tr[x].rs, num);

    up(x, s, t);
}
int check(int T) {
    js = SZ = rt = 0;
    ll orz = 0;

    for (int i = 1; i <= n; ++i) {
        int X1 = max(-T, mu[i].x - T), X2 = min(T, mu[i].x + T);
        int Y1 = max(-T, mu[i].y - T), Y2 = min(T, mu[i].y + T);

        if (X1 > X2 || Y1 > Y2)
            continue;

        seg[++js] = (line) {X1, Y1, Y2, 1}, seg[++js] = (line) {
            X2 + 1, Y1, Y2, -1
        };
    }

    sort(seg + 1, seg + 1 + js, cmp);

    for (int i = 1; i <= js; ++i) {
        if (i != 1)
            orz += 1LL * (seg[i].x - seg[i - 1].x) * tr[rt].v;

        ins(seg[i].l, seg[i].r, -M, M, rt, seg[i].op);
    }

    return orz >= 1LL * (T + T + 1) * (T + T + 1);
}

signed main() {
    while (1) {
        read(n), ++kas;

        if (n == -1)
            break;

        for (int i = 1; i <= n; ++i) read(mu[i].x,mu[i].y);

        int l = 1, r = 1000000, ans = -1;

        while (l <= r) {
            int mid = (l + r) >> 1;

            if (check(mid))
                ans = mid, r = mid - 1;
            else
                l = mid + 1;
        }

        printf("Case %d: ", kas);

        if (ans == -1)
            puts("never");
        else
            printf("%d\n", ans);
    }

    return 0;
}

K

给出一个简单多边形，求最小宽度

$n \leq 100$

注意到你一个宽度是可以有两条平行直线确定的，最优方案肯定存在一种让直线和多边形一边重合的，所以大力扫一下就完事了。

网上一车人用了旋转卡壳，其实不用。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define ri int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	ri v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const int N = 110;


struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){ }
}p[N];
 
typedef Point Vector;
const double esp = 1e-10;
 
int dcmp(double x) {if(fabs(x) < esp) return 0; else return x<0?-1:1;}

 
Vector operator + (Vector A, Vector B) {return Vector(A.x+B.x, A.y+B.y);}
Vector operator - (Vector A, Vector B) {return Vector(A.x-B.x, A.y-B.y);}
Vector operator * (Vector A, double p) {return Vector(A.x*p, A.y*p);}
Vector operator / (Vector A, double p) {return Vector(A.x/p, A.y/p);}
bool operator < (const Point& a, const Point& b){ return a.x<b.x || (a.x==b.x && a.y<b.y);}
bool operator == (const Point& a, const Point& b){return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;}
 
double Dot(Vector A, Vector B){ return A.x*B.x+A.y*B.y; }
double Length(Vector A){return sqrt(Dot(A, A));}
double Angle(Vector A, Vector B) {return acos( Dot(A, B)/Length(A)/Length(B) );}
 
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x ;}
double Area2(Point A, Point B, Point C){return Cross(B-A, C-A); }
 
double DistanceToLine(Point P, Point A, Point B)
{
    Vector v1 = B-A, v2 = P-A;
    //cout << fabs(Cross(v1, v2)) << " " << Length(v1) << " " << fabs(Cross(v1, v2)) / Length(v1) << endl;
    return Cross(v1, v2) / Length(v1);
}

int n,$;

signed main() {
	while (cin >> n) {
        if (!n) return 0;
        for (int i = 1;i <= n;++i) cin >> p[i].x >> p[i].y;
        double minn = 1e20;
        for (int i = 1;i <= n;++i) {
            for (int j = i + 1;j <= n;++j) {
                
                Point l = p[i],r = p[j];

                double maxdis = 0,mindis = 0;
                for (int k = 1;k <= n;++k) {
                    if (k != i && k != j) {
                            //printf("%d %d %lf\n",i,j,DistanceToLine(p[k],l,r));
                            maxdis = max(maxdis,DistanceToLine(p[k],l,r));
                            mindis = min(mindis,DistanceToLine(p[k],l,r));
                        //cout << maxdis << " " << mindis << endl;
                    }
                }
                minn = min(minn,maxdis-mindis);
            }
        }
        minn = ceil(minn * 100) / 100.0;
        printf("Case %d: %.2lf\n",++$, minn);
    }
	return 0;
}

2011 ACM-ICPC World Finals 解题报告

https://doubeecat.cn/post/2011-ACM-ICPC-World-Finals-解题报告/

作者

Doubeecat

发布于

2021-07-05

更新于

2025-09-18

许可协议

关注我

链接

分类

最新文章

归档

标签

2-SAT1
BFS1
BSGS1
CDQ分治1
CV7
CV , transformer1
CV, 分割1
CV, 多模态1
CV,Transformer1
CV,分割2
CV,机器学习1
DFS序1
DL2
DP20
Dijkstra1
Dirchlet 卷积1
ETT1
Kruskal2
Kruskal 重构树2
LCA1
MST2
NTT1
RMQ1
Tarjan4
Transformer2
bitset1
codeforces1
hash1
nim游戏1
transformer1
二分3
二分图1
二维数点1
位运算2
决策单调性1
凸包1
分块2
分治2
分治NTT1
割点1
区间DP2
单调栈3
博弈论1
图论12
多项式1
字符串1
容斥原理2
差分1
差分约束1
并查集2
思维8
扫描线2
拉格朗日插值1
拓扑排序2
搜索1
数位DP2
数学10
数据结构5
数论5
数论分块1
整体二分1
暴力3
最大流2
最小割2
最小环1
最小费用最大流1
最短路3
杜教筛1
构造3
枚举1
树1
树上问题8
树形DP3
树状数组3
树链剖分2
根号分治2
欧拉函数1
毒瘤1
状压DP1
矩阵1
神经网络1
积性函数1
线性DP3
线性基1
线段树8
线段树分治1
组合数学1
缩点1
网络流2
背包5
莫比乌斯反演1
计数问题2
负环1
贪心1
递归2
闵可夫斯基和1
×