Submission #64783

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
const char newl = '\n';
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=Int>
vector<T> read(size_t n){
vector<T> ts(n);
for(size_t i=0;i<n;i++) cin>>ts[i];
return ts;
}
struct Precision{
Precision(){
cout<<fixed<<setprecision(12);
}
}precision_beet;
//INSERT ABOVE HERE
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
Int n;
cin>>n;
vector<Int> xs(n),ys(n);
for(Int i=0;i<n;i++) cin>>xs[i]>>ys[i];
auto cross=[&](Int x1,Int y1,Int x2,Int y2){
return x1*y2-x2*y1;
};
auto area=[&](Int i,Int j,Int k){
i%=n;j%=n;k%=n;
return abs(cross(xs[j]-xs[i],ys[j]-ys[i],xs[k]-xs[i],ys[k]-ys[i]));
};
Int all=0;
for(Int i=1;i<n;i++)
all+=area(0,i,i+1);
Int ans=all;
Int res=0;
for(Int i=0,j=1;i<n;i++){
while(res*2<=all){
res+=area(i,j,j+1);
chmin(ans,abs(all-res-res));
j++;
}
// cout<<all<<' '<<res<<endl;
assert(i+1<j);
res-=area(i,i+1,j);
chmin(ans,abs(all-res-res));
}
cout<<double(ans)/2<<newl;
return 0;
}

ステータス

項目 データ
問題 1455 - はんぶんこ
ユーザー名 syoribu
投稿日時 2020-11-20 12:25:32
言語 C++17
状態 Accepted
得点 7
ソースコード長 1349 Byte
最大実行時間 37 ms
最大メモリ使用量 1556 KB

セット

セット 得点 Cases
1 ALL 7 / 7 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 31 ms 604 KB
1
in2 AC 27 ms 548 KB
1
in3 AC 32 ms 684 KB
1
in4 AC 17 ms 664 KB
1
in5 AC 19 ms 776 KB
1
in6 AC 16 ms 604 KB
1
in7 AC 20 ms 816 KB
1
in8 AC 18 ms 776 KB
1
in9 AC 18 ms 732 KB
1
in10 AC 16 ms 688 KB
1
in11 AC 20 ms 636 KB
1
in12 AC 15 ms 580 KB
1
in13 AC 25 ms 524 KB
1
in14 AC 25 ms 600 KB
1
in15 AC 19 ms 680 KB
1
in16 AC 15 ms 496 KB
1
in17 AC 19 ms 568 KB
1
in18 AC 15 ms 516 KB
1
in19 AC 30 ms 596 KB
1
in20 AC 23 ms 628 KB
1
in21 AC 23 ms 704 KB
1
in22 AC 24 ms 520 KB
1
in23 AC 31 ms 596 KB
1
in24 AC 21 ms 548 KB
1
in25 AC 26 ms 500 KB
1
in26 AC 19 ms 580 KB
1
in27 AC 32 ms 524 KB
1
in28 AC 22 ms 596 KB
1
in29 AC 28 ms 1444 KB
1
in30 AC 37 ms 1536 KB
1
in31 AC 31 ms 1556 KB
1
in32 AC 32 ms 1484 KB
1
in33 AC 32 ms 1280 KB
1
in34 AC 30 ms 1496 KB
1
in35 AC 28 ms 1232 KB
1
in36 AC 31 ms 1508 KB
1
in37 AC 26 ms 1316 KB
1
in38 AC 32 ms 1556 KB
1
in39 AC 31 ms 1376 KB
1
in40 AC 30 ms 1516 KB
1
in41 AC 27 ms 1300 KB
1
in42 AC 26 ms 1384 KB
1