QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686522 | #685. Y-Shaped Knife | Crysfly | WA | 1ms | 8596kb | C++14 | 3.3kb | 2024-10-29 14:01:39 | 2024-10-29 14:01:39 |
Judging History
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;
For(i,1,n)a[i].x=read(),a[i].y=read(),a[i]=a[i].rot(-rang);
// For(i,1,n)cout<<a[i].x<<" "<<a[i].y<<"\n";
//puts("---------");
if(n%3)puts("No"),exit(0);
db l=-1e7,r=1e7+114514;
while(1){
db mid=(l+r)/2;
int ans=chk(mid);
if(ans>0) l=mid;
else r=mid;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8596kb
input:
9 3 -2 -4 6 0 -7 -5 -6 5 1 1 6 -5 0 -3 -7 -4 2
output:
Yes -0.947898626328 -1.669740909437 0.000000000000
result:
ok Answer is found
Test #2:
score: 0
Accepted
time: 0ms
memory: 8400kb
input:
4 568817 -532765 20585 -88674 54620 539081 866306 368203
output:
No
result:
ok No answer
Test #3:
score: 0
Accepted
time: 1ms
memory: 8492kb
input:
3 -249533 -739397 681290 -376732 -942721 799628
output:
Yes 57257.000000000000 -368509.310266604880 0.000000000000
result:
ok Answer is found
Test #4:
score: 0
Accepted
time: 1ms
memory: 7628kb
input:
6 303183 -370732 578892 -257778 328641 25259 660987 62586 -949298 876989 -727181 -390642
output:
Yes 371546.281250000000 -52261.838442375636 0.000000000000
result:
ok Answer is found
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 7788kb
input:
9 302505 -89769 578921 395830 -909766 794824 -13472 -33592 837847 825866 807789 -644604 744094 -411512 -358771 287832 173441 563062
output:
Yes 214401.640625000000 72893.255035444861 0.000000000000
result:
wrong answer Incorrect point count (3/4/2)