QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#394333 | #868. Friendship Circles | Nahidameow | WA | 73ms | 4064kb | C++20 | 6.7kb | 2024-04-20 13:08:40 | 2024-04-20 13:08:41 |
Judging History
answer
#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
bool FileIfstream(std::string name){
std::ifstream f(name.c_str());
return f.good();
}
namespace Math{
ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=2e5+10;
const int mod=998244353;
const long double eps=1e-4;
namespace GeoDouble{
typedef long double DB;
bool equ(DB x,DB y){return fabs(x-y)<=eps;}
int sgn(DB x){return (DB(0)<x)-(x<DB(0));}
namespace VECTOR{
struct vec{
DB x,y;
//=======================================================
vec(){x=y=0;}
vec(DB _x,DB _y){x=_x,y=_y;}
//=======================================================
vec operator + (vec P){return {x+P.x,y+P.y};}
vec operator - (vec P){return {x-P.x,y-P.y};}
vec operator * (DB d){return {x*d,y*d};}
vec operator / (DB d){return {x/d,y/d};}
DB operator | (vec P){return x*P.x+y*P.y;}
DB operator & (vec P){return x*P.y-y*P.x;}
bool operator <(vec P){return y<P.y||(y==P.y&&x<P.x);}
bool operator == (vec P){return equ(x,P.x)&&equ(y,P.y);}
bool operator != (vec P){return !((*this)==P);}
//=======================================================
DB length_Pow(){return x*x+y*y;}
DB length(){return sqrt(length_Pow());}
//vec rotate(DB theta){return {x*cos(theta)-y*sin(theta),x*sin(theta)+y*cos(theta)};}
vec rotate_90(){return {-y,x};}
};
//============================================================
vec operator * (DB d,vec x){return x*d;}
DB dot(vec w,vec t){return w.x*t.x+w.y*t.y;}
DB cross(vec w,vec t){return w.x*t.y-w.y*t.x;}
//============================================================
vec tranlate(vec x,vec y){return x+y;}
DB orient(vec A,vec B,vec C){return (B-A)&(C-A);}
//============================================================
bool isConvex(std::vector<vec> v){
bool hasPos,hasNeg=false;int n=v.size();
for(int i=0;i<n;i++){
auto plc=orient(v[i],v[(i+1)%n],v[(i+2)%n]);
hasPos|=(plc>0);
hasNeg|=(plc<0);
}return !(hasPos&&hasNeg);
}
DB Area(ve<vec>v){
DB ans=0;int L=v.size();
// for(auto &p:v)
// std::cout<<p.x<<' '<<p.y<<'\n';
for(int i=0;i<L;i++)
ans+=(v[i]&v[(i+1)%L]);
return fabs(ans)/2;
}
//=============================================================
struct Line{
vec S;vec v;
//=========================================================
Line(){S=vec();v=vec();}
Line(vec _S,vec _T){S=_S;v=_T-_S;}
//==========================================================
DB Polar(){return atan2(v.y,v.x);}
vec St(){return S;}
vec To(){return S+v;}
bool operator < (Line &P){
return equ(Polar(),P.Polar())?orient(S,P.S,P.S+P.v)>0:Polar()<P.Polar();}
bool operator == (Line P){
return equ(Polar(),P.Polar());}
bool operator != (Line P){
return !((*this)==P);}
};
bool inter(Line l1,Line l2,vec &out){
DB S1=orient(l1.St(),l2.To(),l1.To()),
S2=orient(l1.St(),l2.St(),l1.To());
if(S1==S2)return false;
out=vec((S1*l2.St().x-S2*l2.To().x)/(S1-S2),
(S1*l2.St().y-S2*l2.To().y)/(S1-S2));
return true;
}
ve<vec>HalfArea(ve<Line> L){
sort(all(L));
ve<Line>res;
for(int i=0;i<L.size();i++)
if(res.empty())res.pd(L[i]);
else if(!equ(res.back().Polar(),L[i].Polar()))
res.pd(L[i]);
L=res;
auto down=[&](Line A,Line B,Line C)->bool{
vec U;
assert(inter(B,C,U));
return orient(U,A.St(),A.To())<0;
};
//for(auto &p:L)
// std::cout<<p.St().x<<' '<<p.St().y<<' '<<p.To().x<<' '<<p.To().y<<'\n';
ve<Line>q;
int l=0,r=-1;
for(int i=0;i<L.size();i++){
while(l<r&&down(L[i],q[r],q[r-1]))r--,q.pop_back();
while(l<r&&down(L[i],q[l],q[l+1]))l++;
q.pd(L[i]);r++;//q[++r]=L[i];
// std::cout<<l<<' '<<r<<'\n';
}
while(l<r&&down(q[l],q[r-1],q[r]))r--;
while(l<r&&down(q[r],q[l],q[l+1]))l++;
ve<vec>ans;
for(int i=l;i<r;i++){
vec U;
assert(inter(q[i],q[i+1],U));
ans.pd(U);
}
if(r-l>1){
vec U;
assert(inter(q[r],q[l],U));
ans.pd(U);
}
return ans;
}//input is NiShiZhen,output is NiShiZhen
}
}
using namespace GeoDouble;
using namespace VECTOR;
struct MI{
std::array<long double,3>S;
bool operator < (const MI P)const{
return !equ(S[0],P.S[0])?S[0]<P.S[0]:(!equ(S[1],P.S[1])?S[1]<P.S[1]:(equ(S[2],P.S[2])?false:S[2]<P.S[2]));
}
};
void solve(){
//don't forget to open long long
int n;std::cin>>n;
ve<vec>v(n+1);
for(int i=1;i<=n;i++)std::cin>>v[i].x>>v[i].y;
ve<Line>L;
vec Cor[4]={vec(-1e12,1e12),vec(-1e12,-1e12),vec(1e12,-1e12),vec(1e12,1e12)};
L.pd(Line(Cor[0],Cor[1]));
L.pd(Line(Cor[1],Cor[2]));
L.pd(Line(Cor[2],Cor[3]));
L.pd(Line(Cor[3],Cor[0]));
std::map<MI,int>mp;
auto insert=[&](vec P1,vec P2,int ind)->void{
DB A,B,C;
if(equ(P1.x,P2.x)){
B=0;A=1;C=P1.x;}
else if(equ(P1.y,P2.y)){
A=0;B=1;C=P1.y;}
else{
A=1;
B=-(P1.x-P2.x)/(P1.y-P2.y);
C=-(A*P1.x+B*P1.y);
//assert(C==(-(A*P2.x+B*P2.y)));
}
mp[{A,B,C}]=ind;
};
auto query=[&](vec P1,vec P2)->int{
DB A,B,C;
if(equ(P1.x,P2.x)){
B=0;A=1;C=P1.x;}
else if(equ(P1.y,P2.y)){
A=0;B=1;C=P1.y;}
else{
A=1;
B=-(P1.x-P2.x)/(P1.y-P2.y);
C=-(A*P1.x+B*P1.y);
}
if(mp.find({A,B,C})==mp.end())
return -1;
else return mp[{A,B,C}];
};
for(int i=2;i<=n;i++){
vec S=v[i]-v[1];
vec MD=(v[1]+v[i])/2;
S=S.rotate_90();
vec P1=MD+S,P2=MD-S;
if(orient(v[1],MD,P1)>0)
L.pd(Line(MD,P1));
else L.pd(Line(MD,P2));
insert(MD,P1,i);
}
vec U;
inter(L[6],L[4],U);
// std::cerr<<U.x<<' '<<U.y<<'\n';
ve<vec>P=HalfArea(L);
// for(auto &p:P)
// std::cerr<<p.x<<' '<<p.y<<'\n';
ve<std::pair<vec,int>>vt;
for(int i=2;i<=n;i++)vt.pd({v[i],i});
sort(all(vt),[&](auto &x,auto &y){return x.first.x<y.first.x;});
ve<int>ans;
int sz=P.size();
for(int i=0;i<sz;i++){
int C=query(P[i],P[(i+1)%sz]);
if(C!=-1)
ans.pd(C);
}
sort(all(ans));ans.erase(unique(all(ans)),ans.end());
std::cout<<ans.size()<<' ';
for(auto &p:ans)
std::cout<<p-1<<' ';
std::cout<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
if(!FileIfstream("IO.in")){
freopen("IO.in","w",stdout);
return 0;
}
freopen("IO.in","r",stdin);
freopen("IO.out","w",stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T=1;
std::cin>>T;
while(T--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4064kb
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: 73ms
memory: 4020kb
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...
result:
wrong answer 4961st numbers differ - expected: '3', found: '2'