D - Ball in a Rectangle

题意：小球初始位置在(x,y)，半径为r，以与水平正方向夹角α的初始速度v开始运动，在矩形边框内进行弹性碰撞，问s秒后小球球心位置在哪。

主要做法：浮点数取模。

做法概括：假设最初在(x,y)，由于速度分解后属于弹性碰撞，那么对于每一维单独计算路程，然后用(路程+当前位置)模上周期，即可求得最终位置（需要进行简单判断）

详情见注释

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double pi = acos(-1);
const double eps = 1e-5;
const int maxn = 1e5 + 10;

inline int dcmp(double x)//cmp x with 0
{
    if (fabs(x) <= eps)return 0;
    return x < 0 ? -1 : 1;
}
inline int cmp(double x, double y)
{
    //x>y return 1
    //x<y reutrn -1
    //x==y return 0
    return dcmp(x - y);
}


int main() 
{
    double L, W, x, y, R, a, v, s;
    while (cin >> L >> W >> x >> y >> R >> a >> v >> s)
    {
        if (cmp(R, 0) == 0)break;
        double vx, vy;
        double rad = a / 180.0 * pi;
        L -= 2 * R, W -= 2 * R;//球心运动范围
        double X = 2.0 * L, Y = 2.0 * W;//周期计算
        x -= R, y -= R;//坐标原点变为(R,R)
        vx = v * cos(rad);
        vy = v * sin(rad);//速度分解
        double sx = fmod(x + s * vx, X), sy = fmod(y + s * vy, Y);//求最终位置并对周期取模
        double ansx, ansy;
        ansx = sx, ansy = sy;
        //判断最终答案
        if (-X / 2 < ansx && ansx < X / 2)
            ansx = fabs(ansx);
        else
            ansx = X - fabs(ansx);
        if (-Y / 2 < ansy && ansy < Y / 2)
            ansy = fabs(ansy);
        else
            ansy = Y - fabs(ansy);
        printf("%.2lf %.2lf\n", ansx + R, ansy + R);
    }
    return 0;
}

---

G - Repairing a Road

题意：给一个无向图，每条边有两个参数\(v\)和\(a\)，\(v\)为不操作这条边时的时间代价（后面会讲），你需要从起点\(1\)走到终点\(n\)。其中你拥有一个仅可进行1次的操作，即假设你当前到达点\(i\)的时间为\(ti\)，那么你这个操作就能使这个点所连的边的时间代价变为v*pow(a,-t)。让你求从起点到终点最小的时间代价。

如果没有这一次操作，那么就是个裸的最短路。但是加上了这个操作，那么就需要去判断在哪条边上进行操作，甚至需要在哪个时间点进行这个操作才能达到最优。

做法：先floyd跑出每两点之间的距离，然后去枚举每条边，这样就可以得到这条边的两个端点以及到1到这两个端点的最短路，然后决策什么时间修改这条边最优。

已经推得的公式是:\(f(t)=dis[1][x]+v[i]*pow(a[i],-t)+dis[y][n]\)，其中x，y分别是边i的两个端点，t为啥时候修改枚举的这条边。对f(t)进行求导，得到：\(f'(t)=1 - log(a) * v * pow(a, -t)\)，这个函数显然是单调递增的，并且极值对应的f(t)总是最小值，那么就二分一个t求出这个函数的极值点回带即可用其更新答案。

#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;

const double eps = 1e-5;
const int maxn = 1e5 + 10;

ll mod = 987654321;

int n, m;

int cnt;

struct edge {
    int from, to;
    double v, a;
}e[maxn];

double dis[110][110];

void init()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dis[i][j] = (i == j ? 0 : maxn);
}

void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

double ans;

//f'(t) = 1 - ln(ai) * vi * ai ^ (-t)
double cal(int from, int to, double v, double a)
{
    double l = 0, r = 114514;
    while (r - l > eps)
    {
        //printf("%lf %lf\n", l, r);
        double mid = (l + r) / 2.0;
        if (1 - log(a) * v * pow(a, -mid) > 0)
            r = mid;
        else l = mid;
    }
    double tim;
    if (l < dis[1][from])
        tim = dis[1][from];
    else
        tim = l;
    return tim + v * pow(a, -tim) + dis[to][n];

}

void solve()
{
    for (int i = 1; i <= cnt; i++)
    {
        int from = e[i].from, to = e[i].to;
        double a = e[i].a, v = e[i].v;
        ans = min(ans, cal(from, to, v, a));
        ans = min(ans, cal(to, from, v, a));
    }
}

int main() 
{
    //fastio;
    while (cin >> n >> m, n, m)
    {
        cnt = 0;
        init();
        while (m--)
        {
            int x, y;
            double a, b;
            cin >> x >> y >> a >> b;
            e[++cnt] = { x,y,a,b };
            dis[x][y] = dis[y][x] = a;
        }
        floyd();
        ans = dis[1][n];
        solve();
        printf("%.3lf\n", ans);
    }
    return 0;
}