QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376581 | #868. Friendship Circles | schrodingerstom | WA | 21ms | 10096kb | C++14 | 4.4kb | 2024-04-04 13:15:39 | 2024-04-04 13:15:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
bool memBeg;
template<typename T,typename TT> void chkmin(T &x,TT y) {if(x>y) x=y;}
template<typename T,typename TT> void chkmax(T &x,TT y) {if(x<y) x=y;}
constexpr int mod=998244353;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,ll times,int ret=1) {
for(;times;times>>=1,x=1ll*x*x%mod) if(times&1) ret=1ll*ret*x%mod;
return ret;
}
constexpr int maxn=1e5+10;
constexpr int inf=0x3f3f3f3f;
constexpr ld eps=1e-10;
struct vector2 {
ld x,y;
vector2() {}
vector2(ld _x,ld _y): x(_x),y(_y) {}
vector2 operator+(const vector2 &o) const {return vector2(x+o.x,y+o.y);}
vector2 operator-(const vector2 &o) const {return vector2(x-o.x,y-o.y);}
vector2 operator~() const {return vector2(-y,x);}
vector2 operator*(ld o) const {return vector2(x*o,y*o);}
friend vector2 operator*(const ld &u,const vector2 &v) {return v*u;}
vector2 operator/(ld o) const {return vector2(x/o,y/o);}
friend ld dot(const vector2 &u,const vector2 &v) {return u.x*v.x+u.y*v.y;}
friend ld cross(const vector2 &u,const vector2 &v) {return u.x*v.y-u.y*v.x;}
}pt[maxn];
struct ray {
vector2 o,d;
ray() {}
ray(const vector2 &_o,const vector2 &_d): o(_o),d(_d) {}
friend vector2 inter(const ray &u,const ray &v) {
ld x=cross(v.o-u.o,v.d)/cross(u.d,v.d);
return u.o+x*u.d;
}
void print() const {
if(fabs(d.x)<eps) {
printf("x = %Lf",o.x);
} else {
vector2 u=o,v=o+d;
printf("y = %Lf * (x - %Lf) / (%Lf - %Lf) + %Lf * (x - %Lf) / (%Lf - %Lf)",
v.y,u.x,v.x,u.x,u.y,v.x,u.x,v.x);
}
}
void println(char c='\n') const {
print(); putchar(c);
}
}ln[maxn];
int n,ord[maxn],que[maxn];
ld Arg[maxn];
vector2 it[maxn];
void mian() {
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%Lf%Lf",&pt[i].x,&pt[i].y);
for(int i=1;i<n;i++) ln[i]=ray((pt[0]+pt[i])/2.0L,~(pt[i]-pt[0]));
int top=n+3;
ln[n]=ray(vector2(-inf,-inf),vector2(1,0));
ln[n+1]=ray(vector2(inf,-inf),vector2(0,1));
ln[n+2]=ray(vector2(inf,inf),vector2(-1,0));
ln[n+3]=ray(vector2(-inf,inf),vector2(0,-1));
iota(ord+1,ord+top+1,1);
for(int i=1;i<=top;i++) Arg[i]=atan2l(ln[i].d.y,ln[i].d.x);
sort(ord+1,ord+top+1,[&](int u,int v) {
if(fabs(cross(ln[u].d,ln[v].d))<eps&&dot(ln[u].d,ln[v].d)>eps) {
return cross(ln[u].o-ln[v].o,ln[v].d)<0.0L;
} else return Arg[u]<Arg[v];
});
// for(int i=1;i<=top;i++) ln[ord[i]].println();
// fflush(stdout);
int tead=0,rail=0;
for(int i=1;i<=top;i++) {
if(i>1&&fabs(cross(ln[ord[i]].d,ln[ord[i-1]].d))<eps&&dot(ln[ord[i]].d,ln[ord[i-1]].d)>eps) continue;
if(rail-tead<=1) {
que[rail++]=ord[i];
if(rail-tead>=2) it[rail-2]=inter(ln[que[rail-2]],ln[que[rail-1]]);
} else {
while(rail-tead>1&&cross(it[rail-2]-ln[ord[i]].o,ln[ord[i]].d)>0.0L) rail--;
while(rail-tead>1&&cross(it[tead]-ln[ord[i]].o,ln[ord[i]].d)>0.0L) tead++;
que[rail++]=ord[i];
it[rail-2]=inter(ln[que[rail-2]],ln[que[rail-1]]);
}
// printf("----------i = %d, ord = %d------------:\n",i,ord[i]);
// printf("ln[2] = ((%Lf, %Lf), (%Lf, %Lf))\n",ln[2].o.x,ln[2].o.y,ln[2].d.x,ln[2].d.y);
// for(int j=tead;j<rail;j++) ln[que[j]].println();
// fflush(stdout);
}
while(rail-tead>1&&cross(it[rail-2]-ln[que[tead]].o,ln[que[tead]].d)>0.0L) rail--;
// puts("");
// for(int j=tead;j<rail;j++) ln[que[j]].println();
// fflush(stdout);
assert(rail-tead>2);
vector<int> ret;
for(int i=tead;i<rail;i++) if(que[i]<n) ret.emplace_back(que[i]);
printf("%d ",(int)ret.size());
sort(ret.begin(),ret.end());
for(int v:ret) printf("%d ",v); puts("");
}
bool memEn;
void fl() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
int main() {
fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
// fl();
int _; scanf("%d",&_);
while(_--) mian();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10096kb
input:
2 4 1 0 3 1 3 -2 7 0 5 0 0 -2 -1 2 2 -2 10 -1 11
output:
2 1 2 3 1 2 3
result:
ok 7 numbers
Test #2:
score: -100
Wrong Answer
time: 21ms
memory: 9992kb
input:
10000 10 132243110 -894263225 -965927366 756806080 -563126858 -401644076 -528090722 -199265042 -184232391 -184423675 -346777300 -583114791 624815460 788278140 543172921 980159251 -143672624 674688477 -393343296 525780596 9 64745555 827730910 -665070184 -152609349 -905275127 -345568169 -949821348 -84...
output:
3 4 5 6 5 1 4 6 7 8 1 1 3 1 2 3 2 2 5 3 1 2 3 6 1 2 3 4 5 6 5 1 2 3 4 9 4 1 2 3 4 6 1 2 3 4 5 9 2 1 2 3 1 4 6 5 2 4 5 6 7 4 1 2 4 5 3 1 2 3 3 2 3 6 3 1 6 8 1 1 2 1 2 4 1 4 6 7 5 1 2 4 5 6 3 2 3 4 3 1 3 7 4 1 3 7 9 3 3 4 5 4 3 4 6 8 5 1 3 4 6 7 2 1 2 2 2 3 2 5 6 3 1 2 3 ...
result:
wrong answer 71st numbers differ - expected: '4', found: '3'