QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417069#7906. Almost ConvexLeonardTL 0ms4348kbC++203.6kb2024-05-22 13:59:032024-05-22 13:59:05

Judging History

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

  • [2024-05-22 13:59:05]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4348kb
  • [2024-05-22 13:59:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2010;
struct Point { 
	double x, y; 
	bool operator< (const Point& r){
		if(x != r.x) return x < r.x;
		else return y < r.y;
	}
};        // 点
using Vec = Point;                    // 向量
struct Line { Point P; Vec v; };      // 直线(点向式)
struct Seg { Point A, B; };           // 线段(存两个端点)
struct Circle { Point O; double r; }; // 圆(存圆心和半径)
Point a[N];
using Points = vector<Point>;
const Point O = {0, 0};                        // 原点
const Line Ox = {O, {1, 0}}, Oy = {O, {0, 1}}; // 坐标轴
const double PI = acos(-1), EPS = 1e-9;
bool eq(double a, double b) { return abs(a - b) < EPS; } // ==
bool gt(double a, double b) { return a - b > EPS; }      // >
bool lt(double a, double b) { return a - b < -EPS; }     // <
bool ge(double a, double b) { return a - b > -EPS; }     // >=
bool le(double a, double b) { return a - b < EPS; }      // <=
Vec operator+(Vec u, Vec v) { return {u.x + v.x, u.y + v.y}; }   // 向量加向量
Vec operator-(Vec u, Vec v) { return {u.x - v.x, u.y - v.y}; }   // 向量减向量
Vec operator*(double k, Vec v) { return {k * v.x, k * v.y}; }    // 数乘
double operator*(Vec u, Vec v) { return u.x * v.x + u.y * v.y; } // 点乘
double cross(Vec u, Vec v) { return u.x * v.y - u.y * v.x; } // 叉乘
bool check(Point p, Point q, Point r) // 检查三个点组成的两个向量的旋转方向是否为逆时针
{
    return lt(0, cross(q - p, r - q));
}
Points chull(Points &ps)
{
    sort(ps.begin(), ps.end());
    vector<int> I{0}, used(ps.size());
    for (int i = 1; i < ps.size(); i++)
    {
        while (I.size() > 1 && !check(ps[I[I.size() - 2]], ps[I.back()], ps[i]))
            used[I.back()] = 0, I.pop_back();
        used[i] = 1, I.push_back(i);
    }
    for (int i = ps.size() - 2; i >= 0; i--)
    {
        if (used[i])
            continue;
        while (I.size() > 1 && !check(ps[I[I.size() - 2]], ps[I.back()], ps[i]))
            I.pop_back();
        I.push_back(i);
    }
    Points H;
    for (int i = 0; i < I.size() - 1; i++)
        H.push_back(ps[I[i]]);
    return H;
}
double theta(auto p) { return atan2(p.y, p.x); } // 求极角
void psort(Points &ps, Point c = O)              // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return lt(theta(p1 - c), theta(p2 - c));
    });
}
int n, st[N];
Points v, v1;
struct HashFunc
{
    template<typename T, typename U>
    size_t operator()(const std::pair<T, U>& p) const {
    return std::hash<T>()(p.first) ^ std::hash<U>()(p.second);
    }
};

// 键值比较,哈希碰撞的比较定义,需要直到两个自定义对象是否相等
struct EqualKey {
    template<typename T, typename U>
    bool operator ()(const std::pair<T, U>& p1, const std::pair<T, U>& p2) const {
    return p1.first == p2.first && p1.second == p2.second;
    }
};
unordered_map<std::pair<int, int>, int, HashFunc, EqualKey> vis;
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i].x >> a[i].y;
		v1.push_back(a[i]);
	}
	v = chull(v1);
	for(int i = 0; i < v.size(); i++) vis[{v[i].x, v[i].y}] = 1;
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(!vis[{a[i].x, a[i].y}]){
			Points tmp;
			for(int j=1;j<=n;j++){
				if(j == i) continue;
				tmp.push_back(a[j]);
			}
			psort(tmp, a[i]);
			for(int j=0;j<tmp.size();j++){
                int x = j, y = (j + 1) % (int)tmp.size();
				if(vis[{tmp[x].x, tmp[x].y}] && vis[{tmp[y].x, tmp[y].y}]) ans++;
			}
		}
	}
	cout << ans + 1 << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: