QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#878006 | #685. Y-Shaped Knife | fryan | WA | 0ms | 4096kb | C++20 | 1.7kb | 2025-02-01 12:59:26 | 2025-02-01 12:59:34 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long
#define ld long double
const int mxn = 1e5+5;
const ld pi = 3.1415926535897932;
const ld sq3 = 1.732050807568877293527446341505872366942805253810380628055806;
const ld eps = 1e-10;
int n;
ld ang,x[mxn],y[mxn];
void rot(int i) {
ld xv = x[i]*cos(ang)-y[i]*sin(ang);
ld yv = x[i]*sin(ang)+y[i]*cos(ang);
x[i] = xv, y[i] = yv;
}
vector<pair<ld,int>> pt;
ld yind;
int x_test(ld xv) {
pt.clear();
for (int i=0; i<n; i++) {
ld dist = abs(x[i]-xv);
if (x[i] <= xv) {
pt.push_back({y[i]-dist/sq3,0});
} else {
pt.push_back({y[i]-dist/sq3,1});
}
}
sort(all(pt));
int cnt0 = 0, cnt1 = 1;
for (int i=0; i<2*n/3; i++) {
if (pt[i].second) cnt1++;
else cnt0++;
}
yind = pt[2*n/3].first-1e-5;
if (cnt0 == n/3) return 0;
if (cnt0 < n/3) return -1;
return 1;
}
ld x_search(ld lo, ld hi) {
if (hi-lo < eps) return lo;
ld mid = (lo+hi)/2;
int res = x_test(mid);
if (res==0) return mid;
if (res==-1) return x_search(mid,hi);
return x_search(lo,mid);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cout<<fixed<<setprecision(100);
ang = 0; 1e-8; []() -> long double {
constexpr long double pi = 3.14159265358979323846L;
std::mt19937 gen(std::random_device{}());
return std::uniform_real_distribution<long double>(0.0L, pi)(gen);
}();
cin>>n;
if (n%3) {
cout<<"No\n";
return 0;
}
for (int i=0; i<n; i++) {
cin>>x[i]>>y[i];
rot(i);
}
ld X = x_search(-1e9,1e9+5);
x_test(X);
ld Y = yind;
cout<<"Yes\n"<<X<<" "<<Y<<" "<<ang;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4096kb
input:
9 3 -2 -4 6 0 -7 -5 -6 5 1 1 6 -5 0 -3 -7 -4 2
output:
Yes -1.2252903077751398086547851562500000000000000000000000000000000000000000000000000000000000000000000000 0.3980106122709132205445773516894192312065570149570703506469726562500000000000000000000000000000000000 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Answer is found
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 568817 -532765 20585 -88674 54620 539081 866306 368203
output:
No
result:
ok No answer
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 4096kb
input:
3 -249533 -739397 681290 -376732 -942721 799628
output:
Yes 2.5000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 255346.3334936138040518471825635060667991638183593750000000000000000000000000000000000000000000000000000000 0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer Point 2 is too close to the ray of the tripod