QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#877980 | #685. Y-Shaped Knife | fryan | WA | 1ms | 6256kb | C++20 | 1.7kb | 2025-02-01 12:45:12 | 2025-02-01 12:45:14 |
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;
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);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 6256kb
input:
9 3 -2 -4 6 0 -7 -5 -6 5 1 1 6 -5 0 -3 -7 -4 2
output:
Yes -1.22529 0.398021 0
result:
wrong answer Incorrect point count (3/2/4)