QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#878006#685. Y-Shaped KnifefryanWA 0ms4096kbC++201.7kb2025-02-01 12:59:262025-02-01 12:59:34

Judging History

你现在查看的是最新测评结果

  • [2025-02-01 12:59:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4096kb
  • [2025-02-01 12:59:26]
  • 提交

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