Submission #1545801
Source Code Expand
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <iomanip>
using namespace std;
//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long ll;
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
//container util
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
#define RREP(i,n) RFOR(i,n,0)
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x) cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";
#define X first
#define Y second
const int INF = 1e9;
const int _N = 2e5;
const int _M = 270000;
const long double PI = 3.1415926535897932;
int x1,x2,yy1,yy2;
int n;
int cnt[_N];
int ins = 0;
PII p[_N];
struct SEG{ // min
int d[_M * 2];
int m;
void init(int m){
this->m = m;
REP(i, m * 2 - 1)d[i] = INF;
}
void update(int i, int x){
i += m - 1;
d[i] = x;
while(i>0){
i = (i -1) / 2;
d[i] = min(d[i * 2 + 1], d[i * 2 + 2]);
}
}
int query(int a, int b){
return _query(a, b, 0, 0, m);
}
private:int _query(int a, int b, int k, int l, int r){
if(r <= a || b <= l) return INF;
if(a <= l && r <=b) return d[k];
int vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
};
bool inside(int x, int y){
return x1 <= x && x <= x2 &&
yy1 <= y && y <= yy2;
}
SEG seg;
int main() {
cin >> x1 >> yy1 >> x2 >> yy2 >> n;
//init
REP(i, n)cnt[i] = -1;
int m = 1;
while(m<n)m*=2;
seg.init(m);
//
int xk = 1, yk = 1;
if(x1>x2&&yy1>yy2){
swap(x1,x2);
swap(yy1,yy2);
}else if(x1>x2){
x1*=-1;x2*=-1;
xk=-1;
}else if(yy1>yy2){
yy1*=-1;yy2*=-1;
yk=-1;
}
REP(i, n){
int xx, yy;
cin >> xx >> yy;
p[i] = MP(xx * xk, yy * yk);
}
sort(p, p+n);
int M = 0;
RREP(i,n){
if(!inside(p[i].X, p[i].Y)){
cnt[i] = 0;
seg.update(i, 0);
continue;
}
cnt[i]=-seg.query(i, n);
if(cnt[i]==INF)cnt[i] = 0;
seg.update(i, -cnt[i]);
cnt[i]++;
}
REP(i, n){ //count (right and top) s
M = max(M,cnt[i]);
}
long double ans = (ll)((x2-x1)+(yy2-yy1)) * 100;
cout << fixed << setprecision(13);
if(M==min((x2-x1),(yy2-yy1))+1){
ans += (M-1) * (5*PI - 20) - 20 + 10 * PI;
}else{
ans += M * (5*PI - 20);
}
cout << fixed << setprecision(13) << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
luma |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3173 Byte |
Status |
WA |
Exec Time |
247 ms |
Memory |
4736 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
WA |
2 ms |
2304 KB |
sample_02.txt |
AC |
2 ms |
2304 KB |
sample_03.txt |
AC |
2 ms |
2304 KB |
subtask_1_01.txt |
WA |
2 ms |
2304 KB |
subtask_1_02.txt |
WA |
2 ms |
2304 KB |
subtask_1_03.txt |
WA |
2 ms |
2304 KB |
subtask_1_04.txt |
WA |
2 ms |
2304 KB |
subtask_1_05.txt |
AC |
2 ms |
2304 KB |
subtask_1_06.txt |
AC |
2 ms |
2304 KB |
subtask_1_07.txt |
AC |
2 ms |
2304 KB |
subtask_1_08.txt |
AC |
2 ms |
2304 KB |
subtask_1_09.txt |
AC |
75 ms |
3328 KB |
subtask_1_10.txt |
WA |
159 ms |
4480 KB |
subtask_1_11.txt |
WA |
41 ms |
2816 KB |
subtask_1_12.txt |
WA |
242 ms |
4736 KB |
subtask_1_13.txt |
AC |
170 ms |
4480 KB |
subtask_1_14.txt |
WA |
80 ms |
3328 KB |
subtask_1_15.txt |
WA |
37 ms |
2816 KB |
subtask_1_16.txt |
WA |
246 ms |
4736 KB |
subtask_1_17.txt |
AC |
137 ms |
3456 KB |
subtask_1_18.txt |
WA |
109 ms |
3328 KB |
subtask_1_19.txt |
WA |
105 ms |
3328 KB |
subtask_1_20.txt |
WA |
228 ms |
4736 KB |
subtask_1_21.txt |
WA |
247 ms |
4736 KB |
subtask_1_22.txt |
WA |
246 ms |
4736 KB |
subtask_1_23.txt |
WA |
242 ms |
4736 KB |
subtask_1_24.txt |
AC |
2 ms |
2304 KB |
subtask_1_25.txt |
AC |
2 ms |
2304 KB |
subtask_1_26.txt |
AC |
2 ms |
2304 KB |
subtask_1_27.txt |
AC |
2 ms |
2304 KB |
subtask_1_28.txt |
WA |
177 ms |
4736 KB |
subtask_1_29.txt |
WA |
215 ms |
4736 KB |
subtask_1_30.txt |
WA |
241 ms |
4736 KB |
subtask_1_31.txt |
WA |
192 ms |
4736 KB |
subtask_1_32.txt |
WA |
190 ms |
4736 KB |
subtask_1_33.txt |
WA |
191 ms |
4736 KB |
subtask_1_34.txt |
WA |
189 ms |
4736 KB |
subtask_1_35.txt |
WA |
234 ms |
4736 KB |
subtask_1_36.txt |
WA |
235 ms |
4736 KB |
subtask_1_37.txt |
WA |
239 ms |
4736 KB |
subtask_1_38.txt |
WA |
230 ms |
4736 KB |
subtask_1_39.txt |
WA |
238 ms |
4736 KB |
subtask_1_40.txt |
WA |
230 ms |
4736 KB |
subtask_1_41.txt |
WA |
234 ms |
4736 KB |