QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863664 | #3007. Intersecting Rectangles | isWFnoya# | RE | 0ms | 0kb | C++23 | 3.4kb | 2025-01-19 20:59:37 | 2025-01-19 20:59:43 |
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) ;
cnt = j - i - 1 ;
if(cnt >= k - 2) ans -= c / C(cnt , k - 2) ;
}
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: 0
Runtime Error
input:
100000 -1000000 -1000000 -990000 -990000 -989500 -999999 -979500 -989999 -979000 -999998 -969000 -989998 -968500 -999997 -958500 -989997 -958000 -999996 -948000 -989996 -947500 -999995 -937500 -989995 -937000 -999994 -927000 -989994 -926500 -999993 -916500 -989993 -916000 -999992 -906000 -989992 -90...