2021-team5-005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team5 返回]

[[Image(Standing.png)]][[BR]]
[[Image(Submission.png)]][[BR]]

== 概述 ==

2018-2019 ICPC Southwestern European Regional Programming Contest

== 流水账 ==

开局fx看了A题，报了一边题意，然后发现是个签到A1Y5。czyh发现K也是签到，但签慢了点K1Y25。接下来ckr过了BD，fx过了E B1Y48，E1Y55，D1Y89。fx过了E后czyh把之前开的F丢给fx，让他写极角排序。fx表示不会，czyh表示我会我就自己写了，fx写完之后果然wa。czyh发现他爆精度了，于是打算换个极角排序写法。调试时ckr开始写H的三维偏序，写完了又re又wa（数组开小，建议bg）H3Y139。在修改了若干次F的极角排序后fx表示我不想动这个题了，于是去看C和G。czyh发现fx循环队列写错了（就算最早一发写对也会因为精度问题tle )，修改后AC。F4Y179。czyh改F期间fx和ckr把I读懂了，于是ckr上机写I，I2Y192。czyh这期间在看J但随机几发过不了后去看了看榜上很多的C题，突然发现C有个单词来自词典的隐藏条件，然后push一下fx就过了C2Y224。（样例不测导致wa，建议bg）写完之后fx开始写G，自以为算法很对，但wa；修改后tle，比赛最后10min开始爆oj，czyh试图加头文件、加大数组，无果。fx表示复杂度证明没有问题，可能是算法假了。比赛最后2min，czyh加了个记忆化G8Y299。（讲题时pb将fx的复杂度证明批判一番，证明了这个做法复杂度就是错的）
== 总结 ==

=== Orange_User ===


=== functionendles ===

极角排序不要用atan，要用判象限和叉积

== 题解 ==

A: 签到

B: 一个凸多边形所以如果i行k边长可以那么k+1只要考虑i+k是否可行即可

C: 爆搜

D: 对于同一个x值答案为r[i]-选定值 或者 选定值-l[i] 或者 r[i]-l[i]；那么就是每个x的对应的y的极大极小值的中位数

E:

F: 极角排序+two points

G:

H: 转换为求到0,1,2三点的最短路的三维偏序 cdq分治即可

I: 枚举左上角然后枚举长宽，下面有空洞为A，右边有空洞为C，其余为B 爆搜即可

J:

K: 区间dp

[/wiki/2021-team5 返回]



概述

2018-2019 ICPC Southwestern European Regional Programming Contest

流水账

开局fx看了A题，报了一边题意，然后发现是个签到A1Y5。czyh发现K也是签到，但签慢了点K1Y25。接下来ckr过了BD，fx过了E B1Y48，E1Y55，D1Y89。fx过了E后czyh把之前开的F丢给fx，让他写极角排序。fx表示不会，czyh表示我会我就自己写了，fx写完之后果然wa。czyh发现他爆精度了，于是打算换个极角排序写法。调试时ckr开始写H的三维偏序，写完了又re又wa（数组开小，建议bg）H3Y139。在修改了若干次F的极角排序后fx表示我不想动这个题了，于是去看C和G。czyh发现fx循环队列写错了（就算最早一发写对也会因为精度问题tle )，修改后AC。F4Y179。czyh改F期间fx和ckr把I读懂了，于是ckr上机写I，I2Y192。czyh这期间在看J但随机几发过不了后去看了看榜上很多的C题，突然发现C有个单词来自词典的隐藏条件，然后push一下fx就过了C2Y224。（样例不测导致wa，建议bg）写完之后fx开始写G，自以为算法很对，但wa；修改后tle，比赛最后10min开始爆oj，czyh试图加头文件、加大数组，无果。fx表示复杂度证明没有问题，可能是算法假了。比赛最后2min，czyh加了个记忆化G8Y299。（讲题时pb将fx的复杂度证明批判一番，证明了这个做法复杂度就是错的）

总结

Orange_User

functionendles

极角排序不要用atan，要用判象限和叉积

题解

A: 签到

B: 一个凸多边形所以如果i行k边长可以那么k+1只要考虑i+k是否可行即可

C: 爆搜

D: 对于同一个x值答案为r[i]-选定值 或者 选定值-l[i] 或者 r[i]-l[i]；那么就是每个x的对应的y的极大极小值的中位数

E:

F: 极角排序+two points

G:

H: 转换为求到0,1,2三点的最短路的三维偏序 cdq分治即可

I: 枚举左上角然后枚举长宽，下面有空洞为A，右边有空洞为C，其余为B 爆搜即可

J:

K: 区间dp

附加文件