QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#613205#7906. Almost Convexzhr05TL 1ms4004kbC++232.8kb2024-10-05 13:44:412024-10-05 13:44:45

Judging History

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

  • [2024-10-05 13:44:45]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4004kb
  • [2024-10-05 13:44:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;

int sgn(double x) {
	if(fabs(x) < eps)  return 0;
	else return x<0?-1:1;
}
int Dcmp(double x, double y) {
	if(fabs(x - y) < eps) return 0;
	else return x<y ?-1:1;
}

struct Point {
	double x,y;
	Point(double x,double y):x(x),y(y) {}
	Point() {}
	Point operator + (Point B) {
		return Point(x+B.x,y+B.y);
	}
	Point operator - (Point &B) {
		return Point(x-B.x,y-B.y);
	}

	Point operator + (double rad) {
		return Point(x*cos(rad)-y*sin(rad), x*sin(rad)+y*cos(rad));   //rotate
	}
	Point operator - (double rad) {
		return (*this)+(-rad);
	}
	bool operator == (Point &B) {
		return sgn(x-B.x)==0 && sgn(y-B.y)==0;
	}
	bool operator < (Point &B)  {
		return sgn(x-B.x)<0 || (sgn(x-B.x)==0 && sgn(y-B.y)<0);    //Convex Hull
	}

	double operator * (Point B) {
		return x*B.x + y*B.y;   //Dot
	}
	double operator ^ (Point B) {
		return x*B.y - y*B.x;   //Cross: >0 deg+ dir; <0 deg- dir ;=0 deg=0\180
	}
	double operator ~ () {
		return hypot(x,y);   //Len
	}
};
typedef Point Vec;

// <vec A,vec B>
double Angle(Vec A,Vec B) {
	return acos(A*B/(~A * ~B));
}

//Convex_hull()求凸包。凸包顶点放在ch中,返回值是凸包的顶点数
vector<Point> Convex_hull(vector<Point> &p) {
	sort(p.begin(),p.end());         //对点排序:按x从小到大排序,如果x相同,按y排序
	p.erase(unique(p.begin(),p.end()), p.end());    //remove simi
	int v=0,n=p.size();

	vector<Point> ch;

	for(int i=0; i<n; i++) {
		while(v>1 && sgn((ch[v-1]-ch[v-2])^(p[i]-ch[v-2]))<=0) ch.pop_back(),v--;
		ch.emplace_back(p[i]),v++;
	}//求下凸包。如果p[i]是右拐弯的,这个点不在凸包上,往回退
	int j=v;
	//求上凸包
	for(int i=n-2; i>=0; i--) {
		while(v>j && sgn((ch[v-1]-ch[v-2])^(p[i]-ch[v-2]))<=0) ch.pop_back(),v--;
		ch.emplace_back(p[i]),v++;
	}
	if(n>1) ch.pop_back();
	return ch;   //convex_hull
}

long long Phash(Point A){
	return (long long)A.x*10000000+A.y;
}

vector<Point>P,CH,NCH;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int N;
	cin>>N;
	for(int i=1,xx,yy; i<=N; i++) cin>>xx>>yy,P.emplace_back(xx,yy);
	CH=Convex_hull(P);


	unordered_map<long long,bool> MP;

	for(auto i:CH) MP[Phash(i)]=1;
	for(auto i:P) if(!MP[Phash(i)]) NCH.emplace_back(i);

	int ans=1;
	for(auto k:NCH) {
		//vector<Point>Q;
		//for(auto i:P) if(!(i==k)) Q.emplace_back(i);


		auto cmp=[&](Point A,Point B)->bool{
			if(A==k) return 1;
			if(B==k) return 0;
			return Angle(Point(1,0),A-k)<Angle(Point(1,0),B-k);
		};

		sort(P.begin(),P.end(),cmp);


		for(int i=0,n=P.size(); i<n; i++)
			if(MP[Phash(P[i])] && MP[Phash(P[(i+1)%n])]) ans++;
		if(MP[Phash(P[1])] && MP[Phash(P[P.size()-1])]) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 0ms
memory: 3624kb

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: