[코드] ACM - ICPC 2012 Regionals Asia - Jinhua D Crazy Tank / HDU 4445
13028 단어 ICPC
ACM-ICPC 2012 Regionals Asia - Jinhua D Crazy Tank / HDU 4445
주사 선
Source
http://acm.hdu.edu.cn/showproblem.php?pid=4445
Solution
많은 사람들 이 물 을 건 너 갔 으 니, 나 는 진지 한 스캐닝 라인 을 붙 일 게.
Code
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const double PI = acos(-1.0);
const double EPS = 1e-8;
inline int sgn(double x) {
if (fabs(x)<EPS) return 0;
return x>0?1:-1;
}
int N, M;
double l1, r1, l2, r2;
double v[222];
double g=9.8, h;
double calc(double v, double a) {
double vx = v*cos(a);
double vy = v*sin(a);
double delta = vy*vy+2*g*h;
delta = max(0.0, delta);
double t = (vy+sqrt(delta))/g;
return vx*t;
}
double tri(double l, double r, double v, double &d) {
int cnt = 100;
while (cnt--) {
double m1 = (l+r)/2;
double m2 = (m1+r)/2;
if (calc(v, m1)>calc(v, m2)) r = m2;
else l = m1;
}
d = calc(v, l);
return l;
}
double bin(double l, double r, double d, double v, bool up) {
int cnt = 100;
while (cnt--) {
double m = (l+r)/2;
if ((calc(v, m)<d)^up) l = m;
else r = m;
}
return l;
}
struct se {
double a;
bool in;
int cnt;
se() {}
se(double x, bool y, int z): a(x), in(y), cnt(z) {}
bool operator<(const se &rhs) const {
if (sgn(a-rhs.a)==0) {
return in<rhs.in;
}
return a<rhs.a;
}
}e[9999];
void ae(double a, bool in, int cnt) {
e[M++] = se(a, in, cnt);
}
void solve(double l, double r, double d, double v, double t, int cnt) {
if (sgn(d-l)<0) return;
if (sgn(d-r)<0) {
double hmr = bin(-PI/2, t, l, v, 0);
double mdk = bin(t, PI/2, l, v, 1);
if (sgn(hmr-mdk)>0) while (1) puts("");
ae(hmr, 0, cnt); ae(mdk, 1, -cnt);
return;
}
double s1 = bin(-PI/2, t, l, v, 0);
double t1 = bin(-PI/2, t, r, v, 0);
double s2 = bin(t, PI/2, r, v, 1);
double t2 = bin(t, PI/2, l, v, 1);
if (sgn(s1-t1)>0) while (1) puts("");
if (sgn(s2-t2)>0) while (1) puts("");
if (sgn(t1-s2)>=0) {
ae(s1, 0, cnt); ae(t2, 1, -cnt);
}
else {
ae(s1, 0, cnt); ae(t1, 1, -cnt);
ae(s2, 0, cnt); ae(t2, 1, -cnt);
}
}
char s[111];
int main() {
int i, j, k;
while (cin>>N>>h>>l1>>r1>>l2>>r2, N) {
M = 0;
for (i = 0; i < N; ++i) {
cin>>v[i];
double d, t;
t = tri(-PI/2, PI/2, v[i], d);
solve(l1, r1, d, v[i], t, 1);
solve(l2, r2, d, v[i], t, -998);
}
sort(e, e+M);
int ans = 0;
int cnt = 0;
for (i = 0; i < M; ++i) {
cnt += e[i].cnt;
if (cnt>N) while (1) puts("");
ans = max(ans, cnt);
}
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2013 ACMICPC 항주 라이브 I 문제사고방식: 기억화 검색. dp[S]는 남은 상태가 S일 때 기수가 마법석을 최대 얼마나 얻을 수 있는지 나타낸다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.