QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211398 | #868. Friendship Circles | ucup-team1004 | WA | 22ms | 11704kb | C++14 | 2.9kb | 2023-10-12 15:52:26 | 2023-10-12 15:52:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
using Real=long double;
const int N=1e5+10;
const Real INF=1e12;
struct vec{
Real x,y;
vec(Real a=0,Real b=0):x(a),y(b){}
};
ostream& operator << (ostream &out,const vec &x){
return out<<'('<<x.x<<','<<x.y<<')';
}
vec operator - (const vec &a,const vec &b){
return vec(a.x-b.x,a.y-b.y);
}
vec operator + (const vec &a,const vec &b){
return vec(a.x+b.x,a.y+b.y);
}
vec operator * (const vec &a,const Real &k){
return vec(a.x*k,a.y*k);
}
Real dot(const vec &a,const vec &b){
return a.x*b.x+a.y*b.y;
}
Real cross(const vec &a,const vec &b){
return a.x*b.y-a.y*b.x;
}
vec common(vec a,vec b,vec x,vec y){
Real p=cross(b-x,a-x),q=cross(a-y,b-y);
return x*(q/(p+q))+y*(p/(p+q));
}
int where(const vec &a){
if(!a.y)return a.x>0?0:2;
else return a.y>0?1:3;
}
bool cmp(const vec &a,const vec &b){
int p=where(a),q=where(b);
return p^q?p<q:cross(a,b)>0;
}
int T,n,Ox,Oy;
struct half{
vec s,t;
int id;
}a[N];
ostream& operator << (ostream &out,const half &x){
return out<<'{'<<x.id<<':'<<x.s<<"->"<<x.t<<'}';
}
int q[N],ans[N];
bool chk(int i,int j,int k){
// vec x=a[i].t-a[i].s,y=a[j].t-a[j].s,z=a[k].t-a[k].s;
// if(cross(x,y)<=0||cross(y,z)<=0)return 1;
return cross(a[i].t-a[i].s,common(a[j].s,a[j].t,a[k].s,a[k].t)-a[i].s)>0;
}
int TT;
void get(){
scanf("%d%d%d",&n,&Ox,&Oy),n--;
for(int i=1,x,y;i<=n;i++){
scanf("%d%d",&x,&y);
x-=Ox,y-=Oy;
a[i].s=vec(x,y);
a[i].t=a[i].s+vec(-y,x);
a[i].id=i;
}
// if(++TT==5){
// cout<<n<<endl<<"0 0"<<endl;
// for(int i=1;i<=n;i++){
// printf("%.Lf %.Lf\n",a[i].s.x,a[i].s.y);
// }
// exit(0);
// }
a[++n]={vec(-INF,-INF),vec(INF,-INF),0};
a[++n]={vec(INF,-INF),vec(INF,INF),0};
a[++n]={vec(INF,INF),vec(-INF,INF),0};
a[++n]={vec(-INF,INF),vec(-INF,-INF),0};
sort(a+1,a+1+n,[](half x,half y){
return cmp(x.t-x.s,y.t-y.s);
});
// debug(ary(a,1,n));
// debug(chk(1,2,3));
int L=1,R=0;
for(int i=1;i<=n;i++){
for(;L<R&&!chk(q[R-1],q[R],i);R--);
for(;L<R&&!chk(i,q[L],q[L+1]);L++);
q[++R]=i;
}
for(;L+1<R&&!chk(q[R-1],q[R],q[L]);R--);
fill(ans+1,ans+1+n,0);
for(int i=L;i<=R;i++)ans[a[q[i]].id]=1;
// for(int i=L;i<=R;i++){
// debug(a[q[i]]);
// }
int cnt=accumulate(ans+1,ans+1+n,0);
// if(T>10)return;
printf("%d",cnt);
for(int i=1;i<=n;i++){
if(ans[i])printf(" %d",i);
}
puts("");
}
int main(){
for(scanf("%d",&T);T--;)get();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 11684kb
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: 22ms
memory: 11704kb
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 4 1 2 3 6 3 1 6 8 1 1 2 1 2 5 1 3 4 6 7 5 1 2 4 5 6 3 2 3 4 4 1 3 4 7 4 1 3 7 9 3 3 4 5 4 3 4 6 8 5 1 3 4 6 7 3 1 2 3 2 2 3 3 2 5 6 3 1 2 3 3 2 3 4 4 2 5 6 8 3 ...
result:
wrong answer 4961st numbers differ - expected: '3', found: '2'