QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547606#4371. Spin DoctorPhantomThresholdWA 104ms17644kbC++176.4kb2024-09-04 23:49:422024-09-04 23:49:42

Judging History

你现在查看的是最新测评结果

  • [2024-09-04 23:49:42]
  • 评测
  • 测评结果:WA
  • 用时:104ms
  • 内存:17644kb
  • [2024-09-04 23:49:42]
  • 提交

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);
	if (CHB.size()<=2){
		point st=CHB.front();
		point ed=CHB.back();
		for (auto P:wp) if (inmid(st,ed,P)) ans++;
		cout << ans << "\n";
		return 0;	
	}
	
//	cerr << "---------------------" << endl;
//	cerr << "Convex Hull of black : " << endl;
//	for (auto e:CHB) cerr << e << endl;
//	cerr << "---------------------" << endl;
	
	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=1e9;
	for (auto d:dir){
		int pos=upper_bound(vup.begin(),vup.end(),make_pair(d,0LL),cmp)-vup.begin()-1;
		mn=min(mn,base+sumup[pos]);
	}
	ans+=mn;
	cout << ans << "\n";
	return 0;	
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3504kb

input:

6
0 10 0
10 0 1
12 8 1
5 5 0
11 2 1
11 3 0

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

10
6 1 1
0 2 0
2 1 1
6 1 1
8 2 0
4 4 0
4 0 0
2 3 1
6 1 0
6 3 1

output:

8

result:

ok single line: '8'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

5
5 7 0
3 4 0
5 7 0
5 7 1
9 4 0

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

100
7487 4751 1
7499 5064 1
7471 5376 1
7404 5683 1
7300 5979 1
7159 6260 1
6984 6520 1
6777 6757 1
6543 6966 1
6284 7144 1
6006 7288 1
5711 7396 1
5405 7466 1
5092 7498 1
4780 7490 1
4469 7442 1
4167 7357 1
3878 7234 1
3607 7075 1
3358 6884 1
3135 6664 1
2941 6417 1
2780 6147 1
2653 5860 1
2564 555...

output:

61

result:

ok single line: '61'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

200
7489 1285 0
6851 8471 0
6122 2766 1
2413 9338 0
1725 7382 0
6984 6520 1
5080 8417 0
2604 5711 1
5833 2643 1
48 2810 0
5316 2439 0
900 7419 0
6809 867 0
6006 7288 1
5092 7498 1
5531 2558 1
7075 6393 1
9979 9313 0
7436 4441 1
4595 2534 1
2598 909 0
842 284 0
3358 6884 1
6522 7976 0
604 5833 0
3607...

output:

125

result:

ok single line: '125'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

300
2253 823 1
1865 9556 0
306 6720 1
8588 1519 1
2756 9468 1
5810 9933 1
1625 9138 0
27 932 0
8124 1097 1
8699 8363 1
7202 9489 1
9420 7337 1
9862 6164 1
908 2128 1
9341 2521 1
372 8140 0
9318 7520 1
1760 34 0
785 612 0
1445 1442 0
9694 3280 1
9496 2152 0
9249 1891 0
2162 9828 0
580 2663 1
1269 832...

output:

234

result:

ok single line: '234'

Test #7:

score: 0
Accepted
time: 78ms
memory: 17436kb

input:

100000
7487 4751 1
7487 4751 1
7487 4752 1
7487 4752 1
7487 4752 1
7487 4752 1
7487 4753 1
7487 4753 1
7487 4753 1
7487 4754 1
7487 4754 1
7487 4754 1
7487 4755 1
7487 4755 1
7487 4755 1
7487 4756 1
7488 4756 1
7488 4756 1
7488 4757 1
7488 4757 1
7488 4757 1
7488 4757 1
7488 4758 1
7488 4758 1
7488 ...

output:

68833

result:

ok single line: '68833'

Test #8:

score: 0
Accepted
time: 88ms
memory: 16008kb

input:

100000
8980 4601 1
8980 4602 1
8980 4602 1
8980 4603 1
8980 4603 1
8980 4604 1
8980 4604 1
8980 4605 1
8980 4605 1
8980 4606 1
8980 4606 1
8980 4607 1
8980 4607 1
8980 4608 1
8980 4608 1
8980 4609 1
8980 4609 1
8980 4610 1
8980 4610 1
8980 4611 1
8981 4611 1
8981 4612 1
8981 4612 1
8981 4613 1
8981 ...

output:

79761

result:

ok single line: '79761'

Test #9:

score: 0
Accepted
time: 92ms
memory: 17616kb

input:

100000
9975 4501 1
9975 4502 1
9975 4503 1
9975 4503 1
9975 4504 1
9975 4504 1
9975 4505 1
9975 4506 1
9975 4506 1
9975 4507 1
9975 4508 1
9975 4508 1
9975 4509 1
9975 4509 1
9975 4510 1
9975 4511 1
9976 4511 1
9976 4512 1
9976 4513 1
9976 4513 1
9976 4514 1
9976 4514 1
9976 4515 1
9976 4516 1
9976 ...

output:

79877

result:

ok single line: '79877'

Test #10:

score: 0
Accepted
time: 104ms
memory: 17644kb

input:

100000
89749 223387 0
295171 424382 0
397151 279092 1
393939 207794 1
109069 198636 1
338201 128673 1
388987 306412 1
401174 201459 0
428943 426416 0
292775 106229 1
181076 383227 1
207577 106125 1
389057 405639 0
358258 146173 1
376103 425370 0
284279 396030 1
342155 368352 1
479748 52614 0
102762 ...

output:

72070

result:

ok single line: '72070'

Test #11:

score: 0
Accepted
time: 92ms
memory: 17048kb

input:

100000
649 24758 0
14496 41252 0
39286 10853 0
19975 37285 1
40085 29490 0
1766 27831 0
5842 586 0
27105 8225 1
11312 32491 1
17523 4856 0
16990 8550 1
4916 12992 0
7696 24913 1
42700 5177 0
43755 27268 0
9922 42370 0
8555 16976 1
17794 36896 0
21532 37468 1
35271 30549 0
31468 10477 1
37030 18776 1...

output:

74280

result:

ok single line: '74280'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3
100 100 1
500 500 1
200 200 0

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

5
0 100 0
0 200 1
0 300 0
0 400 1
0 500 0

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

7
100 0 0
200 0 1
300 0 0
400 0 1
500 0 0
600 0 1
700 0 0

output:

5

result:

ok single line: '5'

Test #15:

score: -100
Wrong Answer
time: 0ms
memory: 3552kb

input:

5
0 0 1
100 100 1
50 50 0
50 25 0
25 50 0

output:

5

result:

wrong answer 1st lines differ - expected: '3', found: '5'