QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#613008#7906. Almost Convexzhr05TL 1ms4112kbC++234.1kb2024-10-05 13:25:192024-10-05 13:25:26

Judging History

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

  • [2024-10-05 13:25:26]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4112kb
  • [2024-10-05 13:25:19]
  • 提交

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));
}

//Area
double Area(Point A, Point B, Point C) {
	return ((B-A)^(C-A)) /2.00;
}

struct Line {
	Point p1,p2;//2Points
	Line(Point p1,Point p2):p1(p1),p2(p2) {}
};

bool on_Seg(Point p, Line v) {
	return sgn((p-v.p1)^(v.p2-v.p1)) == 0 && sgn((p - v.p1)*(p- v.p2)) <= 0;
}

//判断点和任意多边形的关系: 3 点上; 2 边上; 1 内部; 0 外部
//点pt,多边形的点Point *p,多边形点的数量n,多边形顶点按照顺时针或者逆时针方向排列
int Point_in_polygon(vector<Point> &p,Point &pt) {
	int n=p.size();
	for(int i = 0; i < n; i++) if(p[i] == pt) return 3;// On_Point
	for(int i = 0; i < n; i++) if(on_Seg(pt,Line(p[i],p[(i+1)%n]))) return 2;// On_Edge

	int num = 0;
	for(int i = 0; i < n; i++) {
		int j = (i+1)% n;
		int c = sgn((pt-p[j])^(p[i]-p[j]));
		int u = sgn(p[i].y - pt.y);
		int v = sgn(p[j].y - pt.y);
		if(c > 0 && u < 0 && v >=0) num++;
		if(c < 0 && u >=0 && v < 0) num--;
	}
	return num != 0; //1-inside; 0-outside
}

double Polygon_area(vector<Point> &p) {
	double area = 0;
	for(int i=0,n=p.size(); i<n; i++)
		area+=p[i]^p[(i+1)%n];
	return area/2;//面积有正负,不能简单地取绝对值
}

//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
}

vector<Point>P,CH,NCH;

bool check(Vec A,Vec B,Vec C) {
	vector<Point>V= {A,B,C};
	for(auto i:NCH) {
		if(i==C) continue;
		if(Point_in_polygon(V,i)) return 0;
	}
	return 1;
}

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);

	map<Point,bool,
	decltype([](auto& p1,auto& p2) {
		return p1.x==p2.x ? p1.y<p2.y:p1.x<p2.x;
	})> MP;

	for(auto i:CH) MP[i]=1;
	for(auto i:P) if(!MP[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[P[i]] && MP[P[(i+1)%n]]) ans++;
		if(MP[P[1]] && MP[P[P.size()-1]]) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

详细

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: