QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#686498#685. Y-Shaped KnifeCrysflyWA 0ms8876kbC++143.3kb2024-10-29 13:53:182024-10-29 13:53:19

Judging History

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

  • [2024-10-29 13:53:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8876kb
  • [2024-10-29 13:53:18]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

typedef double db;
const db eps=1e-8,pi=3.14159265358979323846;
int sgn(db x){return x<-eps?-1:x>eps;}
int cmp(db a,db b){return sgn(a-b);}

struct P{
	db x,y;
	P(db x=0,db y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(db o){return x*=o,y*=o,*this;}
	P&operator /=(db o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,db b){return a*=b;}
	friend P operator /(P a,db b){return a/=b;}
	friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
	friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
	friend bool operator !=(P a,P b){return !(a==b);}
	friend db operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend db operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	
	P rot(db o){
		db s=sin(o),c=cos(o);
		return P(x*c-y*s,x*s+y*c);
	}
	P rot90(){return P(-y,x);}
	db ang(){return atan2(y,x);}
	db len(){return sqrt(x*x+y*y);}
	db len2(){return x*x+y*y;}
	
	int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
	P unit(){return ((*this))/len();}
	
	void read(){cin>>x>>y;}
	void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
	if(a.half()!=b.half())return a.half()<b.half();
	return sgn(a*b)>0;
}

db dis(P a,P b){return (a-b).len();}
db cross(P a,P b,P c){
	// (a->b)*(a->c)
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
	return sgn(cross(a,b,c));
}

#define maxn 200005
#define inf 0x3f3f3f3f

int n;
db rang;
P a[maxn];
mt19937_64 rnd(time(0));

pair<db,int> p[maxn];
db S=1.0/sqrt(3);
int chk(db mid)
{
//	cout<<"chk "<<mid<<"\n";
	For(i,1,n){
		if(a[i].x<mid) p[i]=mkp(a[i].y-(mid-a[i].x)*S,-1);
		else p[i]=mkp(a[i].y-(a[i].x-mid)*S,1);
	}
	sort(p+1,p+n+1);
//	For(i,1,n) cout<<p[i].fi<<" "<<p[i].se<<"\n";
	int pos=n/3*2;
//	nth_element(p+1,p+pos+1,p+n+1);
//	nth_element(p+pos+1,p+pos+2,p+n+1);
	int sum=0;
	For(i,1,pos)sum+=p[i].se;
	if(sum!=0)return sum;
	puts("Yes");
	P tmp=P(mid,(p[pos].fi+p[pos+1].se)/2);
	tmp=tmp.rot(rang);
	printf("%.12lf %.12lf %.12lf\n",tmp.x,tmp.y,rang);
	exit(0);
}

signed main()
{
	n=read();
	rang=1.0*rnd()/ULLONG_MAX*(2*pi/3);
	rang=0.1;
	For(i,1,n)a[i].x=read(),a[i].y=read(),a[i]=a[i].rot(-rang);
	if(n%3)puts("No"),exit(0);
	db l=-1e8,r=1e8;
	while(1){
		db mid=(l+r)/2;
		int ans=chk(mid);
		if(ans>0) l=mid;
		else r=mid;
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 8876kb

input:

9
3 -2
-4 6
0 -7
-5 -6
5 1
1 6
-5 0
-3 -7
-4 2

output:

Yes
-2.882854900380 -1.119661219200 0.100000000000

result:

wrong answer Incorrect point count (3/4/2)