QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863684 | #3001. Piece of Cake | isWFnoya# | WA | 37ms | 4224kb | C++23 | 3.4kb | 2025-01-19 21:13:00 | 2025-01-19 21:13:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std ;
#define vec point
typedef double db ; //卡精度就换long double,不过long double很慢
const db eps = 1e-9 ; //调参
const db pi = acos(-1.0) ;
const db inf = 40000 ;
int sgn(db x)
{
if(x < -eps) return -1 ;
else if (x > eps) return 1 ;
else return 0 ;
}
int cmp(db x , db y)
{
return sgn(x - y) ;
}
void print(int num , db x)
{
cout << fixed << setprecision(num) << x << '\n' ;
}
struct point
{
db x , y ;
point(){}
point(db x2 , db y2)
{
x = x2 , y = y2 ;
}
void input()
{
db x2 , y2 ;
cin >> x2 >> y2 ;
x = x2 ;
y = y2 ;
}
point operator + (const point& s)const{return (point){x + s.x , y + s.y} ;}
point operator - (const point& s)const{return (point){x - s.x , y - s.y} ;}
point operator * (const db& k)const{return (point){x * k , y * k} ;}
point operator / (const db& k)const{return (point){x / k , y / k} ;}
db operator * (const point &a) const {return x*a.x+y*a.y;} //Dot
db operator ^ (const point &a) const {return x*a.y-y*a.x;} //Cross
bool operator < (point b) const
{
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x ;
}
bool equal(point p2)
{
return cmp(x , p2.x) == 0 && cmp(y , p2.y) == 0 ;
}
db get_angle(){return atan2(y , x) ;} //极角
int getP() const{return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1) ;}
db sq(db x) {return x * x ;}
db dis(point p) //很吃精度,可能需要1e-10或更小的eps
{
return sqrtl(sq(x - p.x) + sq(y - p.y)) ; //check sqrt or sqrtl
}
db len()
{
return sqrtl(sq(x) + sq(y)) ;
}
db len2()
{
return sq(x) + sq(y) ;
}
point unit()
{
db w = len() ;
return (point){x / w , y / w} ;
}
vec rotate_left() //向量逆时针旋转90度
{
return vec(-y , x) ;
}
vec rotate_right() //向量顺时针旋转90度
{
return vec(y , -x) ;
}
point move(db r) //原点沿该点代表的向量方向移动r
{
db l = len() ;
if(sgn(l) == 0) return *this ;
else return point(x * r / l , y * r / l) ;
}
vec rotate(db ang) //ang是弧度制,逆时针旋转
{
return vec({x * cos(ang) - y * sin(ang) , y * cos(ang) + x * sin(ang)}) ;
}
} ;
db cross(vec s , vec t){return s.x * t.y - s.y * t.x ;} // 叉积
db fac[3000] ;
db C(int n , int m)
{
if(n <= m) return 1.0 ;
return fac[n] / fac[m] / fac[n - m] ;
}
void solve()
{
fac[0] = 1 ;
for(int i = 1 ; i < 3000 ; i ++) fac[i] = fac[i - 1] * i ;
int n , k ;
cin >> n >> k ;
vector<point> p(n) ;
for(int i = 0 ; i < n ; i ++) p[i].input() ;
reverse(p.begin() , p.end()) ;
db ans = 0 ;
for(int i = 0 ; i < n ; i ++)
for(int j = i + 1 ; j < n ; j ++)
{
db c = cross(p[i] , p[j]) ;
int cnt = n - (j - i + 1) ;
if(cnt >= k - 2) ans += c * C(cnt , k - 2) / C(n , k) ;
cnt = j - i - 1 ;
if(cnt >= k - 2) ans -= c * C(cnt , k - 2) / C(n , k) ;
}
cout << fixed << setprecision(8) << ans / 2 << '\n' ;
}
int main()
{
std::ios::sync_with_stdio(false) , cin.tie(0) ;
int T = 1 ;
// cin >> T ;
while (T --) solve() ;
return 0 ;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4096kb
input:
3 3 -5.236334 -8.519438 -9.987847 -0.492878 -9.994555 0.329962
output:
1.92794640
result:
ok found '1.9279464', expected '1.9279464', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 4224kb
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:
-nan
result:
wrong output format Expected double, but "-nan" found