QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417062 | #7906. Almost Convex | Leonard | TL | 1ms | 4156kb | C++20 | 3.5kb | 2024-05-22 13:54:22 | 2024-05-22 13:54:22 |
Judging History
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++){
if(vis[{tmp[j].x, tmp[j].y}] && vis[{tmp[j+1].x, tmp[j+1].y}]) ans++;
}
}
}
cout << ans + 1 << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4016kb
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: 3948kb
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: 3772kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4156kb
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: 1ms
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...