QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#313616#7906. Almost Convexxiaoxing666TL 1ms3584kbC++173.2kb2024-01-24 21:17:262024-01-24 21:17:26

Judging History

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

  • [2024-01-24 21:17:26]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3584kb
  • [2024-01-24 21:17:26]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long db;
const db EPS = 0;

inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }

inline int cmp(db a, db b){ return sign(a-b); }

struct P {
	db x, y;
	P() {}
	P(db _x, db _y) : x(_x), y(_y) {}
	P operator+(P p) { return {x + p.x, y + p.y}; }
	P operator-(P p) { return {x - p.x, y - p.y}; }
	P operator*(db d) { return {x * d, y * d}; }
	P operator/(db d) { return {x / d, y / d}; }
	
	bool operator<(P p) const { 
		int c = cmp(x, p.x);
		if (c) return c == -1;
		return cmp(y, p.y) == -1;
	}
	
	bool operator==(P o) const{
		return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
	}
	
	db dot(P p) { return x * p.x + y * p.y; }	//点乘
	db det(P p) { return x * p.y - y * p.x; }	//叉乘
	
	db distTo(P p) { return (*this-p).abs(); }
	db alpha() { return atan2(y, x); }
	void read() { cin>>x>>y; }
	void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
	db abs() { return sqrt(abs2());}
	db abs2() { return x * x + y * y; }
	P rot90() { return P(-y,x);}	//旋转90度
	P unit() { return *this/abs(); }
	int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
	P rot(db an){ return {x*cos(an) - y*sin(an),x*sin(an) + y*cos(an)}; }	//旋转任意度
};

#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))		//逆时针正,顺时针负,共线0

vector<P> convexHull(vector<P> ps) {	//严格凸包
	int n = ps.size(); if(n <= 1) return ps;
	sort(ps.begin(), ps.end());
	vector<P> qs(n * 2); int k = 0;
	for (int i = 0; i < n; qs[k++] = ps[i++]) 
		while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
		while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
	qs.resize(k - 1);
	return qs;
}

int n;
vector<P> p;
map<P, int> mp;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		db x, y;
		cin >> x >> y;
		p.push_back({x, y});
	}
	
	int ans = 0;
	vector<P> q = convexHull(p);
	
	for(auto tmp : q)
	{
		mp[tmp] = 1;
	}
	
	vector<P> nw;
	
	for(int i = 0; i < n; i++)
	{
		if(mp[p[i]] == 0)
		{
			nw.push_back(p[i]);
		}
	}
	
	vector<P> con;
	int sz = q.size();
	
	for(auto now : nw)
	{
		con.clear();
		for(auto tmp : p)
		{
			if(tmp == now)
			{
				continue;
			}
			else{
				con.push_back(tmp - now);
			}
		}
		
		for(int i = 0; i < sz; i++)
		{
			int consz = con.size();
			P pre = q[i] - now, nxt = q[(i + 1) % sz] - now;
			sort(con.begin(), con.end(), [&](P a, P b) {
				int qa = a.quad(), qb = b.quad();
				if (qa != qb) return qa < qb;
				else return sign(a.det(b)) > 0;
			});
			
			int l = 0, r = con.size() - 1;
			while(l < r)
			{
				int mid = (l + r) / 2;
				if(pre.quad() == con[mid].quad())
				{
					if(sign(con[mid].det(pre)) > 0)
						l = mid + 1;
					else r = mid;
				}
				else{
					if(pre.quad() > con[mid].quad())
						l = mid + 1;
					else
						r = mid;
				}
			}
			if(con[(l + 1) % consz] == nxt || con[(l - 1 + consz) % consz] == nxt)
				ans++;
		}
	}
	
	cout << ans + 1 << endl;
	
	return 0;
}

详细

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: