QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357932#4371. Spin DoctorCrysflyTL 1ms3600kbC++176.6kb2024-03-19 15:13:162024-03-19 15:13:17

Judging History

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

  • [2024-03-19 15:13:17]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3600kb
  • [2024-03-19 15:13:16]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

typedef double db;
int sgn(int x){return x<0?-1:x>0;}
int cmp(int a,int b){return sgn(a-b);}

struct P{
	int x,y;
	P(int x=0,int y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(int o){return x*=o,y*=o,*this;}
//	P&operator /=(int o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,int b){return a*=b;}
//	friend P operator /(P a,int b){return a/=b;}
	friend bool operator <(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
	friend bool operator ==(P a,P b){return a.x==b.x && a.y==b.y;}
	friend db operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend db operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	
	P rot90(){swap(x,y),x=-x;return *this;}
	db ang(){return atan2(y,x);}
	db l(){return sqrt(x*x+y*y);}
	int l2(){return x*x+y*y;}
	
	int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
//	P unit(){return ((*this))/l();}
	
	void read(){cin>>x>>y;}
	void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
	if(a.half()!=b.half())return a.half()<b.half();
	return sgn(a*b)>0;
}

db dis(P a,P b){return (a-b).l();}
int cross(P a,P b,P c){
	// (a->b)*(a->c)
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
	return sgn(cross(a,b,c));
}

bool paral(P p1,P p2,P q1,P q2){
	// is parallel
	return sgn((p2-p1)*(q2-q1))==0;
}

bool inter(int l1,int r1,int l2,int r2){
	if(l1>r1)swap(l1,r1); if(l2>r2)swap(l2,r2);
	return !(cmp(r1,l2)==-1||cmp(r2,l1)==-1);
}
bool ismid(int a,int m,int b){
	return sgn(a-m)==0||sgn(b-m)==0||((a<m)!=(b<m));
}
bool ismid(P a,P m,P b){
	return ismid(a.x,m.x,b.x)&&ismid(a.y,m.y,b.y);
}

bool isseg(P p1,P p2,P q1,P q2){
	return inter(p1.x,p2.x,q1.x,q2.x) && inter(p1.y,p2.y,q1.y,q2.y) &&
	cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<=0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<=0;
}
bool isseg_strict(P p1,P p2,P q1,P q2){
	return cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<0;
}

struct L{
	P a,b;
	L(P aa,P bb){a=aa,b=bb;}
	bool in(P p){return sgn((b-a)*(p-a))>0;}
	int in_sgn(P p){return sgn((b-a)*(p-a));}
	P dir(){return b-a;}
	bool onl(P p){
		return cmp3(a,b,p)==0;
	}
	bool onseg(P p){
		return onl(p)&&ismid(a,p,b);
	}
	bool onseg_strict(P p){
		return onl(p)&&sgn((p-a)%(a-b))*sgn((p-b)%(a-b))<0;
	}
	void out(){cout<<"("<<a.x<<","<<a.y<<")---("<<b.x<<","<<b.y<<")\n";}
};

bool isseg(L a,L b){
	return isseg(a.a,a.b,b.a,b.b);
}
bool paral(L a,L b){
	// is parallel
	return paral(a.a,a.b,b.a,b.b);
}

bool samedir(L a,L b){
	return paral(a,b) && sgn(a.dir()%b.dir())==1;
}
bool operator <(L a,L b){
	if(samedir(a,b)) return b.in(a.a);
	return cmp_dir(a.dir(),b.dir());
}

db rad(P a,P b){
	return atan2l(a*b,a%b);
}

// polygon
int area(vector<P>a){
	// S*2
	int res=0;
	For(i,0,(int)a.size()-1)res+=a[i]*a[(i+1)%a.size()];
	return res;
}
int contain(vector<P>a,P p){
	int n=a.size(),res=0;
	For(i,0,n-1){
		P u=a[i],v=a[(i+1)%n];
		if(L(u,v).onseg(p))return 1;
		if(cmp(u.y,v.y)<=0)swap(u,v);
		if(cmp(p.y,u.y)>0 || cmp(p.y,v.y)<=0)continue;
		res^=cmp3(p,u,v)>0;
	}
	return res*2;
}

vector<P>convex(vector<P>a){
	int n=a.size(),m=0; if(n<=1)return a;
	sort(a.begin(),a.end());
	vector<P>st(n*2); int tp=0;
	For(i,0,n-1){
		while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	int t=tp;
	Rep(i,n-2,0){
		while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
		st[tp++]=a[i];
	}
	st.resize(tp-1);
	return st;
}

bool in_tri(P a,P b,P c,P p){
	return cmp3(a,b,p)>=0 && cmp3(b,c,p)>=0 && cmp3(c,a,p)>=0;
}
int getid(vector<P>&a,P b){
	int n=a.size(),l=1,r=n-1,res=0;
	while(l<=r){
		int mid=l+r>>1;
		if(cmp3(a[0],a[mid],b)>=0) l=mid+1,res=mid;
		else r=mid-1;
	}
	return res;
}
bool inconvex(vector<P>&a,P b){
	int i=getid(a,b);
	if(i==0)++i;
	if(i+1==a.size())--i;
	return in_tri(a[0],a[i],a[i+1],b);
}

int p0;
int bound(vector<P>&a,P b,int l,int r,int op){
	// 111000
	int n=a.size();
	while(l!=r){
		int mid=l+r>>1;
		if(cmp3(a[mid],a[(mid+1)%n],b)==op) l=mid+1;
		else r=mid;
	}
	return l;
}

vector<P> tanline(vector<P>&a,P b){
	int n=a.size();
	if(b.x<a[0].x){
		int t1=bound(a,b,0,p0-1,-1);
		int t2=bound(a,b,p0,n-1,1);
		return {a[t1],a[t2]};
	}
	int id=getid(a,b);
	int t1=bound(a,b,id+1,n-1,-1);
	int t2=bound(a,b,0,id,1);
	return {a[t1],a[t2]};
}

#define maxn 400005
#define inf 0x3f3f3f3f

int n,sum1,res;
vector<P>a,b;

signed main()
{
	n=read();
	For(_,1,n){
		P p; p.read(); int op=read();
		if(op==1)++sum1,a.pb(p);
		else b.pb(p);
	}
	if(a.size()==1){
		cout<<1<<"\n";
		exit(0);
	}
	a=convex(a);
	if(a.size()==1) {
		int res=0;
		for(auto p:b) if(a[0]==p) ++res;
		cout<<res+sum1<<"\n";
		exit(0);
	}
	if(a.size()==2){
		int res=0;
		for(auto p:b) if(L(a[0],a[1]).onseg(p)) ++res;
		cout<<res+sum1<<"\n";
		exit(0);
	}
	
	p0=0;
	For(i,1,a.size()-1) if(a[p0]<a[i]) p0=i;
//	for(auto p:a)p.out(); puts("---a---");
	
	vector<pair<P,int>>buc;
	int mn=inf,now=0;
	
	for(auto p:b){
		if(inconvex(a,p)){
	//		cout<<"inconvex: ";p.out();
			++sum1;
			continue;
		}
		vector<P> t=tanline(a,p);
	//	cout<<"tan: "; p.out();
		P x=t[0]-p,y=t[1]-p;
	//	x.out(),y.out();
		if(x*y<0)swap(x,y);
		if(x.half()) x=P(0,0)-x,y=P(0,0)-y;
		if(y.half()) y=P(0,0)-y,++now;
		buc.pb(mkp(x,1)),buc.pb(mkp(y,-1));
	}
	
//	cout<<"sum1 "<<sum1<<" "<<now<<"\n";
	
	buc.pb(mkp(P(-1,0),now)),now=0;
	sort(buc.begin(),buc.end(),[&](auto x,auto y){
		if(x.fi*y.fi!=0) return x.fi*y.fi>0;
		return x.se>y.se;
	});
	
	for(int l=0,r;l<buc.size();l=r){
		r=l;
		int s1=0,s2=0;
		while(r<buc.size() && buc[l].fi*buc[r].fi==0){
			if(buc[r].se>0) s1+=buc[r].se;
			else s2+=buc[r].se;
			++r;
		}
		mn=min(mn,now+s1);now+=s1;
		mn=min(mn,now+s2);now+=s2;
	}
	cout<<sum1+mn;
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3544kb

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: 3536kb

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: 1ms
memory: 3536kb

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: 1ms
memory: 3600kb

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: 0ms
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: -100
Time Limit Exceeded

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:


result: