QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547620 | #4371. Spin Doctor | PhantomThreshold | WA | 0ms | 3532kb | C++17 | 6.5kb | 2024-09-05 00:18:10 | 2024-09-05 00:18:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long db;
typedef long long ll;
const db eps=0;
const db INF=1e10;
int sign(db k){
if (k>eps) return 1;
else if (k<-eps) return -1;
return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){x+k1.x,y+k1.y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
db abs2(){
return x*x+y*y;
}
db dis2(point k1){
return ((*this)-k1).abs2();
}
bool operator < (const point &k1) const{
int fl=cmp(x,k1.x);
if (fl==-1) return true;
if (fl==1) return false;
return cmp(y,k1.y)==-1;
}
bool operator == (const point &k1) const{
return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;
}
bool operator > (const point &k1) const{
int fl=cmp(x,k1.x);
if (fl==1) return true;
if (fl==-1) return false;
return cmp(y,k1.y)==1;
}
int getP(){
return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);
}
friend ostream& operator << (ostream &os,const point &k){
os << "(" << k.x << "," << k.y << ")";
return os;
}
};
int inmid(point k1,point k2,point k3){
return inmid(k1.x,k2.x,k3.x) && inmid(k1.y,k2.y,k3.y);
}
db cross(point k1,point k2){
return k1.x*k2.y-k1.y*k2.x;
}
db dot(point k1,point k2){
return k1.x*k2.x+k1.y*k2.y;
}
vector<point> ConvexHull(vector<point> A,int flag=1){
int n=A.size();
vector<point>ans(n*2);
sort(A.begin(),A.end());
int now=-1;
for (int i=0;i<(int)A.size();i++){
while (now>0 && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
ans[++now]=A[i];
}
int pre=now;
for (int i=n-2;i>=0;i--){
while (now>pre && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
ans[++now]=A[i];
}
ans.resize(now);
return ans;
}
struct Convex{
int n;
vector<point> a,upper,lower;
Convex(vector<point> _a):a(_a){
n=a.size();
int ptr=0;
for (int i=1;i<n;i++) if (a[ptr]<a[i]) ptr=i;
for (int i=0;i<=ptr;i++) lower.push_back(a[i]);
for (int i=ptr;i<n;i++) upper.push_back(a[i]);
upper.push_back(a[0]);
}
int sign(long long x){
return x<0?-1:x>0;
}
void update_tangent(const point &p,int id,int &i0,int &i1){
if (cross(a[i0]-p,a[id]-p)>0) i0=id;
if (cross(a[i1]-p,a[id]-p)<0) i1=id;
}
void binary_search(int l,int r,point p,int &i0,int &i1){
if (l==r) return;
update_tangent(p,l%n,i0,i1);
int sl=sign(cross(a[l%n]-p,a[(l+1)%n]-p));
for (;l+1<r;){
int mid=(l+r)/2;
int smid=sign(cross(a[mid%n]-p,a[(mid+1)%n]-p));
if (smid==sl) l=mid;
else r=mid;
}
update_tangent(p,r%n,i0,i1);
}
bool contain(point p){
if (p.x<lower[0].x || p.x>lower.back().x) return false;
int id=lower_bound(lower.begin(),lower.end(),(point){p.x,-INF})-lower.begin();
if (lower[id].x==p.x){
if (lower[id].y>p.y) return false;
}
else if (cross(lower[id-1]-p,lower[id]-p)<0)
return false;
id=lower_bound(upper.begin(),upper.end(),(point){p.x,INF},greater<point>())-upper.begin();
if (upper[id].x==p.x){
if (upper[id].y<p.y) return false;
}
else if (cross(upper[id-1]-p,upper[id]-p)<0) return false;
return true;
}
bool get_tangent(point p,int &i0,int &i1){
if (contain(p)) return false;
i0=i1=0;
int id=lower_bound(lower.begin(),lower.end(),p)-lower.begin();
binary_search(0,id,p,i0,i1);
binary_search(id,(int)lower.size(),p,i0,i1);
id=lower_bound(upper.begin(),upper.end(),p,greater<point>())-upper.begin();
binary_search((int)lower.size()-1,(int)lower.size()-1+id,p,i0,i1);
binary_search((int)lower.size()-1+id,(int)lower.size()-1+(int)upper.size(),p,i0,i1);
return true;
}
};
int main(){
int n;
cin >> n;
vector<point> wp;
vector<point> bp;
db cntw=0,cntb=0;
for (int i=1;i<=n;i++){
db x,y;
int col;
cin >> x >> y >> col;
if (col==0){
cntw++;
wp.emplace_back((point){x,y});
}
else{
cntb++;
bp.emplace_back((point){x,y});
}
}
if (cntb==1){
cout << 1 << "\n";
return 0;
}
db ans=cntb;
sort(bp.begin(),bp.end());
bp.resize(unique(bp.begin(),bp.end())-bp.begin());
vector<point> CHB=bp;
if (bp.size()>=3) CHB=ConvexHull(bp);
// cerr << "---------------------" << endl;
// cerr << "Convex Hull of black : " << endl;
// for (auto e:CHB) cerr << e << endl;
// cerr << "---------------------" << endl;
if (CHB.size()<=2){
point st=CHB.front();
point ed=CHB.back();
for (auto P:wp) if (inmid(st,ed,P) && sign(cross(P-st,ed-st))==0) ans++;
cout << ans << "\n";
return 0;
}
ll base=0;
Convex conv(CHB);
vector<point> dir;
vector<pair<point,ll>> vup;
for (auto P:wp){
int st=0,ed=0;
bool flag=conv.get_tangent(P,st,ed);
if (!flag){
ans++;
continue;
}
point dirst=CHB[st]-P;
point dired=CHB[ed]-P;
if (sign(cross(dirst,dired))<0) swap(dirst,dired);
if (dirst.getP()) dirst=dirst*(-1);
if (dired.getP()) dired=dired*(-1);
dir.emplace_back(dirst);
dir.emplace_back(dired);
vup.emplace_back(dirst,1LL);
vup.emplace_back(dired,-1LL);
if (sign(cross(dirst,dired))<0) base++;
}
dir.emplace_back((point){1,0});
sort(dir.begin(),dir.end(),
[&](const point &X,const point &Y){
return sign(cross(X,Y))>0;
}
);
dir.resize(
unique(dir.begin(),dir.end(),
[&](const point &X,const point &Y){
return sign(cross(X,Y))==0;
}
)
-dir.begin()
);
dir.emplace_back((point){-1,0});
{
vector<point> tmp;
int sz=dir.size();
for (int i=0;i<=sz-2;i++){
tmp.emplace_back(dir[i]);
tmp.emplace_back(dir[i]+dir[i+1]);
}
swap(dir,tmp);
}
// cerr << "ans : " << ans << endl;
// for (auto d:dir){
// cerr << "dir : " << d << endl;
// }
auto cmp = [&](const pair<point,ll> &X,const pair<point,ll> &Y){
int flag=sign(cross(X.first,Y.first));
if (flag!=0) return flag==1;
return X.second>Y.second;
};
sort(vup.begin(),vup.end(),cmp);
vector<ll> sumup(vup.size()+1);
if (vup.size()) sumup[0]=vup[0].second;
for (int i=1;i<(int)vup.size();i++) sumup[i]=sumup[i-1]+vup[i].second;
// for (auto [vec,val]:dir){
// cerr << "vec,val : " << vec << " " << val << endl;
// }
ll mn=base;
for (auto d:dir){
int pos=upper_bound(vup.begin(),vup.end(),make_pair(d,0LL),cmp)-vup.begin()-1;
if (pos>0) mn=min(mn,base+sumup[pos]);
}
ans+=mn;
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3532kb
input:
6 0 10 0 10 0 1 12 8 1 5 5 0 11 2 1 11 3 0
output:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'