QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410078#7906. Almost ConvexfwggTL 3ms13580kbC++144.2kb2024-05-13 11:15:282024-05-13 11:15:28

Judging History

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

  • [2024-05-13 11:15:28]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:13580kb
  • [2024-05-13 11:15:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
//
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define qwq ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define QWQ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define jump ;return 0;
#define space " "
#define line '\n'
#define m0(a) memset((a),0,sizeof(a));
#define mINF(a) memset((a),0x3f,sizeof(a));
#define mNINF(a) memset((a),-0x3f,sizeof(a));
#define mNeg(a) memset((a),-1,sizeof(a));
using mainint = signed;using ll = long long;using ull = unsigned long long;using ld = long double;template<class T>void gmin(T &a,T b){if(a>b) a=b;}template<class T>void gmax(T &a,T b){if(a<b) a=b;}using pii=pair<int,int>;using pll=pair<ll,ll>;using pil=pair<int,ll>;using Pli=pair<ll,int>;const int INF=0x3f3f3f3f;const ll INFINF=0x3f3f3f3f3f3f3f3f;
mt19937 rnd(time(0)); 
uniform_int_distribution<long long> dist(0, 1000000000);

#include <ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

const double eps=1e-8;
const double pi=acos(-1.0);
int sgn(double x){
	if(fabs(x)<eps) return 0;
	if(x>0) return 1;
	return -1;
}
struct point{
	double x,y;
	int id;
	point(){x=0,y=0;}
	point(double _x,double _y){
		x=_x,y=_y;
	}
	point operator +(point b){return point(x+b.x,y+b.y);}
	point operator -(point b){return point(x-b.x,y-b.y);}
	double operator *(point b){return x*b.x+y*b.y;}//点只因
	double operator ^(point b){return x*b.y-y*b.x;}//叉只因,逆正顺负
	double distoO(){return sqrt(x*x+y*y);}
	double getlength(){return sqrt(x*x+y*y);}
	void transXY(double B){ 
		double tx=x,ty=y;
		x=tx*cos(B)-ty*sin(B); 
		y=tx*sin(B)+ty*cos(B);
	}
	friend ostream& operator <<(ostream& output,point a){
		output<<a.x<<" "<<a.y<<" ";
		return output;
	}
	
};
int Quadrant(point a)
{
    if(a.x>0&&a.y>=0)  return 1;
    if(a.x<=0&&a.y>0)  return 2;
    if(a.x<0&&a.y<=0)  return 3;
    if(a.x>=0&&a.y<0)  return 4;
	return 0;
}
bool cmp_chaji(point a,point b){
	point c(0,0);
	int op=sgn((a-c)^(b-c));
	if(op>0) return 1;
	if(op==0) return a.x<b.x;
	return 0;
}
bool operator <(point a,point b){
	// if(atan2(a.y,a.x)!=atan2(b.y,b.x))
		return atan2(a.y,a.x)<atan2(b.y,b.x);//或者预处理
	// return a.x<b.x;
}
// bool operator <(point a,point b){
// 	if(Quadrant(a)!=Quadrant(b)) return Quadrant(a)<Quadrant(b);
// 	return cmp_chaji(a,b);
// }

point middle;
bool cmp(point a,point b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
	double opa=(middle^a),opb=(middle^b);
	double dela=(middle*a)/(middle.distoO()*a.distoO());
	double delb=(middle*b)/(middle.distoO()*b.distoO());
	if(sgn(opa-opb)==0){
		if(sgn(opa)==1) return dela<delb;
		else return dela<delb;
	}
	return sgn(opa)>sgn(opb);
}
point p[200005];
point sta[200005];
int n;
int all=0;
double andrew(){
	sort(p+1,p+1+n,cmp);
	int top=0;
	for(int i=1;i<=n;++i){
		while(top>=2 && sgn((sta[top]-sta[top-1])^(p[i]-sta[top-1]))<=0) top--;
		sta[++top]=p[i];
	}
	int k=top;
	for(int i=n-1;i>=1;--i){
		while(top>k && sgn((sta[top]-sta[top-1])^(p[i]-sta[top-1]))<=0) top--;
		sta[++top]=p[i];
	}
	if(n>1) top--;//有时候不需要
	return top;
}
bool on_id[200005];
vector<point> on,off;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>p[i].x>>p[i].y,p[i].id=i;
	int len=andrew();
	for(int i=1;i<=len;++i) on_id[sta[i].id]=1,on.push_back(sta[i]);
	for(int i=1;i<=n;++i)
		if(on_id[p[i].id]==0) off.push_back(p[i]);
	ll ans=1;
	for(auto u:off){
		// cout<<"u:"<<u<<'\n';
		middle=u;
		tree<point, null_type, less<point>, rb_tree_tag, tree_order_statistics_node_update> T;
		for(auto v:off){
			if(!(u.x==v.x && u.y==v.y))
				T.insert(v-u);
		}
		// for(auto j:T) cout<<atan2(j.y,j.x)<<'\n';
		for(int i=0;i<on.size();++i){
			T.insert(on[i]-u);T.insert(on[(i+1)%on.size()]-u);
			
			// cout<<on[i]-u<<space<<
			// T.order_of_key(on[i]-u)<<space<<
			// (on[(i+1)%on.size()]-u)<<space<<T.order_of_key(on[(i+1)%on.size()]-u)<<'\n';
			int L=T.order_of_key(on[i]-u),R=T.order_of_key(on[(i+1)%on.size()]-u),S=T.size();
			if((L+1)%S==(R)){
				ans++;
				// cout<<"⊙";
			}
			T.erase(on[i]-u);T.erase(on[(i+1)%on.size()]-u);
		}
	}
	cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 3ms
memory: 13472kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 3ms
memory: 13248kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:


result: