首页 > 代码库 > 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;}
hdu 4401 Battery
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。