QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884140#9869. Horizon Scanninggaliyuu#WA 1ms3968kbC++235.2kb2025-02-05 21:33:392025-02-05 21:33:40

Judging History

This is the latest submission verdict.

  • [2025-02-05 21:33:40]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3968kb
  • [2025-02-05 21:33:39]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define endl '\n'
#define SZ(x) ((ll)(x).size())
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double db;
mt19937 mrand(random_device{}());
int rnd(int x){return mrand()%x;}
const ll mod=998244353;

long double PI=acos(-1.0); // 180
using T=long double; // 还是不要乱动免得精度爆炸
constexpr T EPS=1e-10;
constexpr T INF=1e20;
 
inline int sign(T a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(T a, T b) { return sign(a-b); }
inline T pow2(T x) { return x*x; }
 
struct P {
    T x, y;
    P(T _x=0, T _y=0) : x(_x), y(_y) {} 
    P operator+() { return *this; }
    P operator-() { return P(-x,-y); }
    P operator+(P p) { return P(x + p.x, y + p.y); }
    P operator-(P p) { return P(x - p.x, y - p.y); }     
    P operator*(T k) { return P(x * k, y * k); }
    P operator/(T k) { return P(x / k, y / k); }
 
    bool operator<(P p) const { 
        int c = cmp(x, p.x);
        if (c) return c == -1;
        return cmp(y, p.y) == -1;
    }
 
    // (a == b and b == c) != (a == c)
    bool operator==(P &p) { return cmp(p.x,x) == 0 and cmp(p.y,y) == 0; }
     
    T dot(P p) { return x * p.x + y * p.y; }
    T det(P p) { return x * p.y - y * p.x; } // an = this->p
 
    T abs2() { return x * x + y * y; }
    T abs() { return sqrt(abs2()); }
    T distTo(P p) { return (*this - p).abs(); } // distanct(this,p)
    P rot90() { return P(-y,x); } // 逆时针
    P unit() { return *this/abs(); }
    P rot(T an){ return {x*cos(an)-y*sin(an),x*sin(an)+y*cos(an)}; } // 顺时针
    // quad [0,pi)-1, [pi,2pi)-0.
    // 判断是在 x 轴上半段还是下半段
    int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
 
    T alpha() { return atan2(y, x); } // atan2l-(long double) 
    T angle(P p) { return acos(((*this).dot(p))/abs()/p.abs()); }
};
ostream &operator<<(ostream &os,const P &p) {
    return os << p.x << " " << p.y;
}
istream &operator>>(istream &is,P &p) {
    is >> p.x >> p.y;
    return is;
}
 
// crossOp==0 三点共线 crossOp==1/-1 p3 在 p2 逆/顺时针
// crossOp 在 10-9 处可能会出现一定的精度问题
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
 
bool chkLL(P p1, P p2, P q1, P q2) { // 两条 直线 是否相交
    T a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
    return sign(a1+a2) != 0;
}
P isLL(P p1, P p2, P q1, P q2) { // 求 直线 交点
    T a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
    return (p1 * a2 + p2 * a1) / (a1 + a2);
}
bool intersect(T l1,T r1,T l2,T r2) { // 判断 [l1,r1] 与 [l2,r2] 是否相交
    if(l1>r1) swap(l1,r1); if(l2>r2) swap(l2,r2); 
    return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}
bool isSS(P p1, P p2, P q1, P q2) { // 线段相交
    return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) && 
    crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
            * crossOp(q1,q2,p2) <= 0;
}
bool isSS_strict(P p1, P p2, P q1, P q2) { // 线段严格相交 不能交端点
    return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
            * crossOp(q1,q2,p2) < 0;
} 
bool isMiddle(T a, T m, T b) { 
    return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b) { // 判断一个点是否在平面中间
    return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
bool onSeg(P p1, P p2, P q) { // 判断 点 q 是不是在线段 p1p2 上
    return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
} 
bool onSeg_strict(P p1, P p2, P q) { 
    return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
P proj(P p1, P p2, P q) { // 求 q 到 直线p1p2 的投影 (垂足), p1 != p2!
    P dir = p2 - p1;
    return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
P reflect(P p1, P p2, P q) { // 求 q 以 直线p1p2 为轴的反射, p1 != p2!
    return proj(p1,p2,q) * 2 - q;
} 
T nearest(P p1,P p2,P q){ // 求 q 到 线段 p1p2 的最小距离
    if (p1==p2) return p1.distTo(q);
    P h = proj(p1,p2,q);
    if(isMiddle(p1,h,p2)) 
        return q.distTo(h);
    return min(p1.distTo(q),p2.distTo(q));
}
T disSS(P p1, P p2, P q1, P q2) { // 求 线段 p1p2 与 线段 q1q2 的距离
    if(isSS(p1,p2,q1,q2)) return 0;
    return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}


signed main() {
	int tc;
	scanf("%d",&tc);
	while (tc--) {
		int n,k;
		scanf("%d%d",&n,&k);
		vector<db> pa(2*n);
		rep(i,0,n) {
			P a;
			cin>>a;
			pa[i]=a.alpha();
		}
		if (n==1) {
			db ans=2*PI;
			printf("%.10f\n",ans);
			continue;
		}
		sort(pa.begin(),pa.begin()+n);
		rep(i,n,2*n) pa[i]=pa[i-n]+2*PI;
		db ans;
		ans=pa[k]-pa[0];
		rep(i,k+1,2*n) {
			ans=max(ans,pa[i]-pa[i-k]);
		} 
		printf("%.10f\n",ans);
	}
}

// 8 2
// 1 0
// 1 1
// 0 1
// -1 1
// -1 0
// -1 -1
// 0 -1
// 1 -1

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3968kb

input:

5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000

result:

wrong answer 1st numbers differ - expected: '6.2831853', found: '0.0000000', error = '1.0000000'