QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#863783 | #3001. Piece of Cake | isWFnoya# | AC ✓ | 32ms | 131076kb | C++26 | 2.5kb | 2025-01-19 22:20:28 | 2025-01-19 22:20:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
#define double long double
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
// int a[N],b[N];
double a[N],b[N];
char s[N];
double C[3000][3000];
double pw[N];
bool check(double K,double B,double x,double y){
if(y>K*x+B) return true;
return false;
}
void __(){
// cin>>n>>m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
for(int i=1;i<=n*2;i++){
a[i+n]=a[i];
b[i+n]=b[i];
// a[i+n]=a[i];
// b[i+n]=b[i];
}
double ans=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]==a[j]) continue;
double K=(b[j]-b[i])/(a[j]-a[i]);
double B=b[i]-a[i]*K;
double res=(b[i]+b[j])*fabs(a[i]-a[j])/2;
// cout<<"--"<<res<<" ";
double rres=(C[j-i-1][m-2]-C[n-(j-i+1)][m-2])/C[n][m];
rres*=res;
// if(j==i+2){
// cout<<j-i-1<<" "<<m-2<<" "<<n-(j-i+1)<<" "<<C[j-i-1][m-2]/C[n][m]<<" "<<C[n-(j-i+1)][m-2]/C[n][m]<<endl;
// cout<<rres<<endl;
// }
// if(j==i+1){
bool flag=0;
if(j==i+n-1){
if(check(K,B,a[i+1],b[i+1])){
// double rres=
ans-=rres;
}else{
// double rres=(val[j-i-1][m-2]-val[n-(j-i+1)][m-2])*res;
ans+=rres;
}
}else
if(check(K,B,a[j+1],b[j+1])){
// double rres=
ans+=rres;
}else{
// double rres=(val[j-i-1][m-2]-val[n-(j-i+1)][m-2])*res;
ans-=rres;
}
// }
// cout<<i<<" "<<j<<" "<<rres<<" "<<ans<<endl;
}
}
// printf("%.20f\n",ans);
cout << fixed << setprecision(20) << ans<< '\n' ;
}
int main(){
for(int i=0;i<=2550;i++){
C[i][0]=1;
}
for(int i=1;i<=2550;i++){
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1]);
}
}
pw[0]=1;
for(int i=1;i<=2550;i++) pw[i]=pw[i-1]*2;
// val[0][0]=0;
// for(int i=0;i<=10;i++){
// for(int j=0;j<=10;j++) cout<<val[i][j]<<" ";
// cout<<endl;
// }
int _=1;
// cin>>_;
while(_--){
__();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 128896kb
input:
3 3 -5.236334 -8.519438 -9.987847 -0.492878 -9.994555 0.329962
output:
1.92794639622000000276
result:
ok found '1.9279464', expected '1.9279464', error '0.0000000'
Test #2:
score: 0
Accepted
time: 31ms
memory: 131072kb
input:
2496 3 -9.999961 0.028130 -9.999655 0.083151 -9.999641 0.084830 -9.999572 0.092537 -9.999474 0.102653 -9.999366 0.112678 -9.999329 0.115862 -9.998360 0.181104 -9.998033 0.198381 -9.997191 0.237035 -9.995264 0.307754 -9.993680 0.355494 -9.992454 0.388414 -9.992180 0.395407 -9.992030 0.399190 -9.99086...
output:
47.71453707054831559764
result:
ok found '47.7145371', expected '47.7145371', error '0.0000000'
Test #3:
score: 0
Accepted
time: 27ms
memory: 131072kb
input:
2099 1049 -9.999906 0.043015 -9.999734 0.072371 -9.999721 0.074260 -9.999602 0.089189 -9.999407 0.108349 -9.999328 0.115856 -9.998818 0.153747 -9.998136 0.193060 -9.997663 0.216208 -9.997463 0.225142 -9.996961 0.246480 -9.995978 0.282576 -9.995847 0.287087 -9.995567 0.296415 -9.994353 0.335674 -9.99...
output:
267.94895542030522925248
result:
ok found '267.9489554', expected '267.9489554', error '0.0000000'
Test #4:
score: 0
Accepted
time: 9ms
memory: 130944kb
input:
342 171 -9.998818 0.153747 -9.997917 0.202726 -9.997663 0.216208 -9.986909 0.482051 -9.977066 0.669980 -9.960055 0.892895 -9.943677 1.059735 -9.924803 1.223737 -9.922265 1.244011 -9.881584 1.527686 -9.871340 1.595884 -9.813970 1.916653 -9.787551 2.050325 -9.745125 2.243053 -9.683458 2.495799 -9.6678...
output:
266.64419338279892054966
result:
ok found '266.6441934', expected '266.6441934', error '0.0000000'
Test #5:
score: 0
Accepted
time: 9ms
memory: 129028kb
input:
87 86 7.934712 5.851277 7.957370 5.901363 7.984885 5.912160 8.057904 5.888196 8.090706 5.871558 8.192155 5.734764 8.214245 5.702976 8.241768 5.663321 8.314438 5.556037 8.394960 5.433442 8.425523 5.386110 8.474268 5.308844 8.497539 5.271774 8.565648 5.160298 8.580590 5.135443 8.621362 5.066710 8.6895...
output:
3.22685463652795977109
result:
ok found '3.2268546', expected '3.2268546', error '0.0000000'
Test #6:
score: 0
Accepted
time: 32ms
memory: 131076kb
input:
2496 2471 -9.999961 0.028130 -9.999655 0.083151 -9.999641 0.084830 -9.999572 0.092537 -9.999474 0.102653 -9.999366 0.112678 -9.999329 0.115862 -9.998360 0.181104 -9.998033 0.198381 -9.997191 0.237035 -9.995264 0.307754 -9.993680 0.355494 -9.992454 0.388414 -9.992180 0.395407 -9.992030 0.399190 -9.99...
output:
314.15727131421242696030
result:
ok found '314.1572713', expected '314.1572713', error '0.0000000'
Test #7:
score: 0
Accepted
time: 30ms
memory: 129028kb
input:
2379 1903 0.001241 9.999987 0.003330 9.999997 0.007027 9.999997 0.015799 9.999987 0.018521 9.999982 0.034934 9.999938 0.040716 9.999917 0.046881 9.999888 0.053865 9.999854 0.055231 9.999847 0.061980 9.999806 0.069431 9.999758 0.077677 9.999698 0.080054 9.999679 0.094173 9.999552 0.100783 9.999492 0....
output:
28.53590957066725335850
result:
ok found '28.5359096', expected '28.5359096', error '0.0000000'