打卡信奥刷题（3236）用C++实现信奥题 P8452 「SWTR-8」15B03-程序员充电站

P8452 「SWTR-8」15B03

题目背景

15B03 获得了 ION2064 的承办权。

题目描述

15B03 的座位非常拥挤，可以看成一张n × m n\times mn×m的网格，每个小正方形( i , j ) (i, j)(i,j)代表一张桌子。

根据规定，考场上任何两张桌子不得相邻。这里相邻指含有公共点。严格定义两张桌子( i , j ) (i, j)(i,j)和( i ′ , j ′ ) (i', j')(i′,j′)相邻当且仅当∣ i − i ′ ∣ ≤ 1 |i - i'|\leq 1∣i−i′∣≤1且∣ j − j ′ ∣ ≤ 1 |j - j'|\leq 1∣j−j′∣≤1。

布置考场的任务落在小 A 头上，他希望撤去最少的桌子满足上述要求。

小 A 认为这样太简单了，因此他添加了限制：在保证撤去桌子最少的前提下，最大化剩余每张桌子到距离它最远的桌子的距离之和。这里距离指欧几里得距离：桌子( a , b ) (a, b)(a,b)和( c , d ) (c, d)(c,d)的距离为( a − c ) 2 + ( b − d ) 2 \sqrt{(a - c) ^ 2 + (b - d) ^ 2}(a−c)2+(b−d)2。

平行时空中 15B03 的规模不尽相同：多组测试数据。

请选手认真阅读本题的评分方式。

输入格式

第一行一个整数S SS，表示该测试点的编号。

第二行一个整数T TT，表示数据组数。接下来T TT组测试数据，每组数据形如：

一行两个整数n , m n, mn,m。

输出格式

对于每组测试数据：

输出一个整数和一个实数，由空格隔开。分别表示最少撤去的桌子数量以及每张桌子到距离它最远的桌子的距离之和的最大值。

实数比较按绝对误差或相对误差不超过10 − 9 10 ^ {-9}10−9：令你输出的答案为a aa，标准答案为b bb，你的答案被判为正确当且仅当∣ a − b ∣ max ⁡ ( 1 , ∣ b ∣ ) ≤ 10 − 9 \frac{|a - b|}{\max(1, |b|)} \leq 10 ^ {-9}max(1,∣b∣)∣a−b∣≤10−9。

输入输出样例 #1

输入 #1

0 4 3 3 2 4 15 57 1064 822

输出 #1

5 11.313708499 6 6.324555320 623 10206.135788972 655956 222400384.677931725

说明/提示

「样例解释」

对于第一组询问，选择( 1 , 1 ) , ( 1 , 3 ) , ( 3 , 1 ) (1, 1), (1, 3), (3, 1)(1,1),(1,3),(3,1)和( 3 , 3 ) (3, 3)(3,3)最优。撤去了3 × 3 − 4 = 5 3\times 3 - 4 = 53×3−4=5张桌子，且每张桌子到距离它最远的桌子的距离均为2 2 + 2 2 = 2 2 \sqrt{2 ^ 2 + 2 ^ 2} = 2\sqrt 222+22=22，因此第二问答案为8 2 8\sqrt 282。如下图所示：

对于第二组询问，选择( 1 , 1 ) (1, 1)(1,1)和( 2 , 4 ) (2, 4)(2,4)最优。撤去了2 × 4 − 2 = 6 2\times 4 - 2 = 62×4−2=6张桌子，且每张桌子到距离它最远的桌子的距离均为1 2 + 3 2 = 10 \sqrt{1 ^ 2 + 3 ^ 2} = \sqrt {10}12+32=10，因此第二问答案为2 10 2\sqrt {10}210。

如果选择( 1 , 1 ) (1, 1)(1,1)和( 2 , 3 ) (2, 3)(2,3)，则第二问答案为2 5 2\sqrt 525，不优。

「评分方式」

对于每组测试数据：

若你第一问的答案错误，得 0 分。
否则，若你第二问的答案错误，得 0.8 分。
否则，得 1 分。

每个测试点的得分为测试点内所有测试数据的得分的最小值乘以该测试点的分值。

注意，若你输出的格式错误，得 0 分。因此，如果你只希望获得第一问的分数，请在第二问输出任意合理范围内的实数。

「数据范围与约定」

测试点 #1（15 points）：n , m n, mn,m均为奇数。
测试点 #2（20 points）：n = 1 n = 1n=1。
测试点 #3（25 points）：n = 2 n = 2n=2。
测试点 #4（30 points）：n nn为奇数。
测试点 #5（10 points）：无特殊限制。

对于100 % 100\%100%的数据：

1 ≤ T ≤ 57 1\leq T\leq 571≤T≤57。
1 ≤ n , m ≤ 1064 1\leq n, m\leq 10641≤n,m≤1064。

「帮助与提示」

你可以使用cmath中的sqrt(x)函数计算x xx的平方根。它返回double类型的值。sqrtl(x)精度更高，它返回long double类型的值。

「题目来源」

Sweet Round 8 A
Idea & Solution：Alex_Wei。
Tester：chenxia25。

C++实现

#include<bits/stdc++.h>#definelllonglongusingnamespacestd;ll s,t,n,m,r;intmain(){std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s>>t;for(inti=1;i<=t;i++){boolp=1,q=1;cin>>n>>m;r=n*m;if(n%2==0)n--,p=0;if(m%2==0)m--,q=0;r-=(n/2+1)*(m/2+1);cout<<r<<" ";if(p==0)n++;if(q==0)m++;if(n*m-r==1){cout<<"0.000000000"<<endl;continue;}longdoubleans=0.0;longlongk=1,j=1;p=1,q=1;for(k=1;k<=n;k+=2){q=1;for(j=1;j<=m;j+=2){if(m%2==0&&j>(m/2)&&(q))j++,q=0;longlongx,y;if(k<=(n+1)/2)x=k;elsex=n-k+1;if(j<=(m+1)/2)y=j;elsey=m-j+1;ans+=sqrtl(((longdouble)((n-x)*(n-x))+((longdouble)((m-y)*(m-y)))));}if(n%2==0&&k+2>=(n/2)&&(p))k++,p=0;}cout<<fixed<<setprecision(9)<<ans<<endl;}return(0-0);}