QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#877980#685. Y-Shaped KnifefryanWA 1ms6256kbC++201.7kb2025-02-01 12:45:122025-02-01 12:45:14

Judging History

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

  • [2025-02-01 12:45:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6256kb
  • [2025-02-01 12:45:12]
  • 提交

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;
	
	
	
}

詳細信息

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)