/ Vijos / 题库 / 物理实验 /

题解

3 条题解

  • 1
    @ 2023-07-12 17:40:06 
    #include<bits/stdc++.h>
using namespace std;
const int MAXN = 40005;
const double eps = 1e-6;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
    x = 0; int f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}
template <typename T> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
    write(x);
    puts("");
}
struct point {double x, y; };
struct segment {point a, b; };
point operator + (point a, point b) {return (point) {a.x + b.x, a.y + b.y}; }
point operator - (point a, point b) {return (point) {a.x - b.x, a.y - b.y}; }
double operator * (point a, point b) {return a.x * b.y - a.y * b.x; }
point operator * (point a, double b) {return (point) {a.x * b, a.y * b}; }
point operator / (point a, double b) {return (point) {a.x / b, a.y / b}; }
double moo(point a) {return sqrt(a.x * a.x + a.y * a.y); }
double dot(point a, point b) {return a.x * b.x + a.y * b.y; }
point unit(point a) {return a / moo(a); }
double gety (segment a, double x) {
    point tmp = a.b - a.a;
    tmp = tmp / (a.b.x - a.a.x) * (x - a.a.x);
    return (a.a + tmp).y;
}
struct info {int val; };
struct changes {double x; int home; bool type; };
segment a[MAXN], goal;
point axisx, axisy;
changes c[MAXN];
int length, tot; double nowx;
int upsum; double upx[MAXN], uprate[MAXN];
int downsum; double downx[MAXN], downrate[MAXN];
int cnt; double x[MAXN], rate[MAXN], sum[MAXN];
set <info> st;
bool cmptype;
bool operator < (info x, info y) {
    if (cmptype) return gety(a[x.val], nowx) < gety(a[y.val], nowx);
    return gety(a[x.val], nowx) > gety(a[y.val], nowx);
}
bool operator < (changes a, changes b) {
    return a.x < b.x;
}
point vary(point a) {
    point ans;
    a = a - goal.a;
    ans.x = dot(axisx, a);
    ans.y = dot(axisy, a);
    return ans;
}
int main() {
    int T; read(T);
    while (T--) {
        int n; read(n);
        for (int i = 1; i <= n; i++) {
            read(a[i].a.x), read(a[i].a.y);
            read(a[i].b.x), read(a[i].b.y);
        }
        read(goal.a.x), read(goal.a.y);
        read(goal.b.x), read(goal.b.y);
        read(length);
        axisx = unit(goal.b - goal.a);
        axisy = (point) {-axisx.y, axisx.x};
        for (int i = 1; i <= n; i++) {
            a[i].a = vary(a[i].a);
            a[i].b = vary(a[i].b);
            if (a[i].a.x > a[i].b.x) swap(a[i].a, a[i].b);
        }
        //getup
        tot = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i].a.y > 0) {
                c[++tot] = (changes) {a[i].a.x, i, true};
                c[++tot] = (changes) {a[i].b.x, i, false};
            }
        }
        sort(c + 1, c + tot + 1);
        cmptype = true;
        st.clear();
        upsum = tot;
        for (int i = 1; i <= tot; i++) {
            nowx = c[i].x;
            upx[i] = c[i].x;
            if (c[i].type) st.insert((info) {c[i].home});
            else st.erase((info) {c[i].home});
            if (st.empty()) uprate[i] = 0;
            else {
                int tmp = (*st.begin()).val;
                point tnp = a[tmp].b - a[tmp].a;
                tnp = tnp / tnp.x; uprate[i] = moo(tnp);
            }
        }
        //getup
        //getdown
        tot = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i].a.y < 0) {
                c[++tot] = (changes) {a[i].a.x, i, true};
                c[++tot] = (changes) {a[i].b.x, i, false};
            }
        }
        sort(c + 1, c + tot + 1);
        cmptype = false;
        st.clear();
        downsum = tot;
        for (int i = 1; i <= tot; i++) {
            nowx = c[i].x;
            downx[i] = c[i].x;
            if (c[i].type) st.insert((info) {c[i].home});
            else st.erase((info) {c[i].home});
            if (st.empty()) downrate[i] = 0;
            else {
                int tmp = (*st.begin()).val;
                point tnp = a[tmp].b - a[tmp].a;
                tnp = tnp / tnp.x; downrate[i] = moo(tnp);
            }
        }
        //getdown
        int upnow = 1, downnow = 1;
        double upr = 0, downr = 0; cnt = 0;
        while (upnow <= upsum || downnow <= downsum) {
            if (upnow > upsum) x[++cnt] = downx[downnow];
            else if (downnow > downsum) x[++cnt] = upx[upnow];
            else if (upx[upnow] < downx[downnow]) x[++cnt] = upx[upnow];
            else x[++cnt] = downx[downnow];
            while (upnow <= upsum && abs(x[cnt] - upx[upnow]) < eps) upr = uprate[upnow++];
            while (downnow <= downsum && abs(x[cnt] - downx[downnow]) < eps) downr = downrate[downnow++];
            rate[cnt] = upr + downr;
        }
        for (int i = 2; i <= cnt; i++)
            sum[i] = sum[i - 1] + rate[i - 1] * (x[i] - x[i - 1]);
        double ans = 0;
        for (int i = 1; i <= cnt - 1; i++) {
            double now = 0, tx = x[i] + length;
            if (tx >= x[cnt]) now = sum[cnt] - sum[i];
            else {
                int l = i, r = cnt;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (tx >= x[mid]) l = mid;
                    else r = mid - 1;
                }
                now = sum[r] - sum[i] + (tx - x[r]) * rate[r];
            }
            chkmax(ans, now);
        }
        for (int i = cnt; i >= 2; i--) {
            double now = 0, tx = x[i] - length;
            if (tx <= x[1]) now = sum[i];
            else {
                int l = 1, r = i;
                while (l < r) {
                    int mid = (l + r) / 2;
                    if (tx <= x[mid]) r = mid;
                    else l = mid + 1;
                }
                now = sum[i] - sum[r] + (x[r] - tx) * rate[r - 1];
            }
            chkmax(ans, now);
        }
        printf("%.3f\n", ans);
    }
    return 0;
}
  • 1
    @ 2020-12-12 18:33:36 
    #include<bits/stdc++.h>
using namespace std;
const int MAXN = 40005;
const double eps = 1e-6;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
    x = 0; int f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}
template <typename T> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
    write(x);
    puts("");
}
struct point {double x, y; };
struct segment {point a, b; };
point operator + (point a, point b) {return (point) {a.x + b.x, a.y + b.y}; }
point operator - (point a, point b) {return (point) {a.x - b.x, a.y - b.y}; }
double operator * (point a, point b) {return a.x * b.y - a.y * b.x; }
point operator * (point a, double b) {return (point) {a.x * b, a.y * b}; }
point operator / (point a, double b) {return (point) {a.x / b, a.y / b}; }
double moo(point a) {return sqrt(a.x * a.x + a.y * a.y); }
double dot(point a, point b) {return a.x * b.x + a.y * b.y; }
point unit(point a) {return a / moo(a); }
double gety (segment a, double x) {
    point tmp = a.b - a.a;
    tmp = tmp / (a.b.x - a.a.x) * (x - a.a.x);
    return (a.a + tmp).y;
}
struct info {int val; };
struct changes {double x; int home; bool type; };
segment a[MAXN], goal;
point axisx, axisy;
changes c[MAXN];
int length, tot; double nowx;
int upsum; double upx[MAXN], uprate[MAXN];
int downsum; double downx[MAXN], downrate[MAXN];
int cnt; double x[MAXN], rate[MAXN], sum[MAXN];
set <info> st;
bool cmptype;
bool operator < (info x, info y) {
    if (cmptype) return gety(a[x.val], nowx) < gety(a[y.val], nowx);
    return gety(a[x.val], nowx) > gety(a[y.val], nowx);
}
bool operator < (changes a, changes b) {
    return a.x < b.x;
}
point vary(point a) {
    point ans;
    a = a - goal.a;
    ans.x = dot(axisx, a);
    ans.y = dot(axisy, a);
    return ans;
}
int main() {
    int T; read(T);
    while (T--) {
        int n; read(n);
        for (int i = 1; i <= n; i++) {
            read(a[i].a.x), read(a[i].a.y);
            read(a[i].b.x), read(a[i].b.y);
        }
        read(goal.a.x), read(goal.a.y);
        read(goal.b.x), read(goal.b.y);
        read(length);
        axisx = unit(goal.b - goal.a);
        axisy = (point) {-axisx.y, axisx.x};
        for (int i = 1; i <= n; i++) {
            a[i].a = vary(a[i].a);
            a[i].b = vary(a[i].b);
            if (a[i].a.x > a[i].b.x) swap(a[i].a, a[i].b);
        }
        //getup
        tot = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i].a.y > 0) {
                c[++tot] = (changes) {a[i].a.x, i, true};
                c[++tot] = (changes) {a[i].b.x, i, false};
            }
        }
        sort(c + 1, c + tot + 1);
        cmptype = true;
        st.clear();
        upsum = tot;
        for (int i = 1; i <= tot; i++) {
            nowx = c[i].x;
            upx[i] = c[i].x;
            if (c[i].type) st.insert((info) {c[i].home});
            else st.erase((info) {c[i].home});
            if (st.empty()) uprate[i] = 0;
            else {
                int tmp = (*st.begin()).val;
                point tnp = a[tmp].b - a[tmp].a;
                tnp = tnp / tnp.x; uprate[i] = moo(tnp);
            }
        }
        //getup
        //getdown
        tot = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i].a.y < 0) {
                c[++tot] = (changes) {a[i].a.x, i, true};
                c[++tot] = (changes) {a[i].b.x, i, false};
            }
        }
        sort(c + 1, c + tot + 1);
        cmptype = false;
        st.clear();
        downsum = tot;
        for (int i = 1; i <= tot; i++) {
            nowx = c[i].x;
            downx[i] = c[i].x;
            if (c[i].type) st.insert((info) {c[i].home});
            else st.erase((info) {c[i].home});
            if (st.empty()) downrate[i] = 0;
            else {
                int tmp = (*st.begin()).val;
                point tnp = a[tmp].b - a[tmp].a;
                tnp = tnp / tnp.x; downrate[i] = moo(tnp);
            }
        }
        //getdown
        int upnow = 1, downnow = 1;
        double upr = 0, downr = 0; cnt = 0;
        while (upnow <= upsum || downnow <= downsum) {
            if (upnow > upsum) x[++cnt] = downx[downnow];
            else if (downnow > downsum) x[++cnt] = upx[upnow];
            else if (upx[upnow] < downx[downnow]) x[++cnt] = upx[upnow];
            else x[++cnt] = downx[downnow];
            while (upnow <= upsum && abs(x[cnt] - upx[upnow]) < eps) upr = uprate[upnow++];
            while (downnow <= downsum && abs(x[cnt] - downx[downnow]) < eps) downr = downrate[downnow++];
            rate[cnt] = upr + downr;
        }
        for (int i = 2; i <= cnt; i++)
            sum[i] = sum[i - 1] + rate[i - 1] * (x[i] - x[i - 1]);
        double ans = 0;
        for (int i = 1; i <= cnt - 1; i++) {
            double now = 0, tx = x[i] + length;
            if (tx >= x[cnt]) now = sum[cnt] - sum[i];
            else {
                int l = i, r = cnt;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (tx >= x[mid]) l = mid;
                    else r = mid - 1;
                }
                now = sum[r] - sum[i] + (tx - x[r]) * rate[r];
            }
            chkmax(ans, now);
        }
        for (int i = cnt; i >= 2; i--) {
            double now = 0, tx = x[i] - length;
            if (tx <= x[1]) now = sum[i];
            else {
                int l = 1, r = i;
                while (l < r) {
                    int mid = (l + r) / 2;
                    if (tx <= x[mid]) r = mid;
                    else l = mid + 1;
                }
                now = sum[i] - sum[r] + (x[r] - tx) * rate[r - 1];
            }
            chkmax(ans, now);
        }
        printf("%.3f\n", ans);
    }
    return 0;
}
  • -1
    @ 2020-12-12 18:26:17

    太BT了吧

  • 1

物理实验

信息

ID
2046
难度
4
分类
(无)
标签
递交数
29
已通过
14
通过率
48%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1