首页 > 代码库 > hdu 4401 Battery

hdu 4401 Battery

这里只给出代码,感兴趣的可以作以参考:

 

技术分享
#include <algorithm>#include <cstdio>#include <cstring>#include <string>#include <queue>#include <map>#include <set>#include <stack>#include <ctime>#include <functional>#include <cmath>#include <iostream>#include <assert.h>#pragma comment(linker, "/STACK:102400000,102400000")#define max(a, b) ((a) > (b) ? (a) : (b))#define min(a, b) ((a) < (b) ? (a) : (b))#define mp std :: make_pair#define st first#define nd second#define keyn (root->ch[1]->ch[0])#define lson (u << 1)#define rson (u << 1 | 1)#define pii std :: pair<int, int>#define pll pair<ll, ll>#define pb push_back#define type(x) __typeof(x.begin())#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)#define FOR(i, s, t) for(int i = (s); i <= (t); i++)#define ROF(i, t, s) for(int i = (t); i >= (s); i--)#define dbg(x) std::cout << x << std::endl#define dbg2(x, y) std::cout << x << " " << y << std::endl#define clr(x, i) memset(x, (i), sizeof(x))#define maximize(x, y) x = max((x), (y))#define minimize(x, y) x = min((x), (y))using namespace std;typedef long long ll;const int int_inf = 0x3f3f3f3f;const ll ll_inf = 0x3f3f3f3f3f3f3f3f;const int INT_INF = (int)((1ll << 31) - 1);const double double_inf = 1e30;const double eps = 1e-14;const double pi = acos(-1.);typedef unsigned long long ul;typedef unsigned int ui;inline int readint() {    int x;    scanf("%d", &x);    return x;}inline int readstr(char *s) {    scanf("%s", s);    return strlen(s);}class cmpt {public:    bool operator () (const int &x, const int &y) const {        return x > y;    }};int Rand(int x, int o) {    //if o set, return [1, x], else return [0, x - 1]    if (!x) return 0;    int tem = (int)((double)rand() / RAND_MAX * x) % x;    return o ? tem + 1 : tem;}ll ll_rand(ll x, int o) {    if (!x) return 0;    ll tem = (ll)((double)rand() / RAND_MAX * x) % x;    return o ? tem + 1 : tem;}void data_gen() {    srand(time(0));    freopen("in.txt", "w", stdout);    int kases = 100;    //printf("%d\n", kases);    while (kases--) {        int L = Rand(1000, 1) + 5;        int n = Rand(L - 4, 1) + 3;        int buf[1500], p = 0;        FOR(i, 1, n) buf[i] = Rand(L, 0);        buf[++n] = 0, buf[++n] = L;        sort(buf + 1, buf + n + 1);        n = unique(buf + 1, buf + n + 1) - buf - 1;        printf("%d %d\n", L, n);        int t1 = Rand(13, 0) + 6;        int t2 = Rand(13, 0) + 6;        while (t2 == t1) {            t2 = Rand(13, 0) + 6;        }        if (t1 > t2) swap(t1, t2);        printf("%d %d\n", t1, t2);        FOR(i, 1, n) {            printf("%d %d\n", buf[i], Rand(1000, 1));        }        puts("\n");    }    puts("0 0");}const int maxn = 1e3 + 10;pii a[maxn];int n, L;int t1, t2;struct Line {    int lhs, rhs;    double theta;    int o;    Line() {}    Line(int _lhs, int _rhs, double _ta, int _o) {        lhs = _lhs, rhs = _rhs, theta = _ta, o = _o;    }    bool operator < (const Line &other) {        return theta > other.theta || theta == other.theta && rhs > other.rhs ||            theta == other.theta && rhs == other.rhs && lhs > other.lhs;    }}lines[maxn * maxn];int k;double shadow, H;bool inq[maxn];double cal(double theta1, double theta2) {    if (abs(theta1 - theta2) < eps) return 0;    double X = abs(theta1 - pi / 2) < eps ? 0 : H / tan(theta1);    double ret = (cos(theta2) - cos(theta1)) * (L - shadow + X) - H * (sin(theta1) - sin(theta2));    shadow += abs(theta2) < eps ? L - shadow : H / tan(theta2) - X;    return ret;}double solve(int l, int r) {    shadow = H = 0;    k = 0;    FOR(i, 2, n) {        inq[i] = 1;        H += a[i].nd;        double mini = (double)ll_inf;        int mk = 0;        ROF(j, i - 1, 1) {            double ang_tan = (double)a[i].second / (a[i].first - a[j].first);            lines[k++] = Line(j, i, atan(ang_tan), 0);            if (a[i].second <= a[j].second) break;            ang_tan = (double)(a[i].second - a[j].second) / (a[i].first - a[j].first);            lines[k++] = Line(j, i, atan(ang_tan), 1);        }    }    double ang_l = pi / 12 * (18 - l), ang_r = pi / 12 * (18 - r);    lines[k++] = Line(0, 0, ang_l, 2), lines[k++] = Line(0, 0, ang_r, 3);    sort(lines, lines + k);    double ans = 0;    bool okay = false;    double pre = pi / 2;    FOR(i, 0, k - 1) {        int o = lines[i].o;        int lhs = lines[i].lhs, rhs = lines[i].rhs;        double ang = lines[i].theta;        double res = cal(pre, ang);        if (okay) ans += res;        if (o == 3) break;        else if (o == 2) okay = true;        else if (o == 0 && inq[rhs]) inq[rhs] = 0, H -= a[rhs].nd, mk = 1;        else if (o == 1 && inq[lhs]) H += a[rhs].nd - a[lhs].nd, inq[lhs] = 0, inq[rhs] = 1, mk = 1;        pre = ang;    }    return abs(ans * 12 / pi);}int main() {    //data_gen(); return 0;    //C(); return 0;    int debug = 0;    if (debug) freopen("in.txt", "r", stdin);    //freopen("out.txt", "w", stdout);    int kases = 0;    while (~scanf("%d%d", &L, &n) && n) {        ++kases;        t1 = readint(), t2 = readint();        FOR(i, 1, n) scanf("%d%d", &a[i].st, &a[i].nd);        double ans = 0;        if (t1 >= 12) ans += solve(t1, t2);        else {            if (t2 > 12) ans += solve(12, t2), t2 = 12;            FOR(i, 1, n) a[i].first = L - a[i].st;            FOR(i, 1, n / 2) swap(a[i], a[n + 1 - i]);            ans += solve(24 - t2, 24 - t1);        }        printf("%.5f\n", ans);    }    return 0;}
View Code

 

hdu 4401 Battery