이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#include "trilib.h"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void ordena(vector<int> &v)
{
if (v.size() <= 1) return;
vector<int> l, r;
for (int i = 1; i < v.size(); i++)
{
// cerr << "||1 " << v[0] << " " << v[i] << '\n';
if (is_clockwise(1, v[0], v[i])) l.push_back(v[i]);
else r.push_back(v[i]);
}
ordena(l); ordena(r);
l.push_back(v[0]);
v = l;
for (auto x : r) v.push_back(x);
}
int main()
{
int N = get_n();
vector<int> points(N-1);
iota(points.begin(), points.end(), 2);
shuffle(points.begin(), points.end(), rng);
ordena(points);
vector<int> hull; bool putOne = 0;
for (int i = 0; i < N-1; i++)
{
hull.push_back(points[i]);
// cerr << "i: " << i << "||1 " << points[i] << " " << points[(i+1)%(N-1)] << '\n';
if (!putOne && is_clockwise(1, points[i], points[(i+1)%(N-1)])) {putOne = 1; hull.push_back(1);}
}
for (int i = 0; i < hull.size(); i++)
{
int tam = hull.size();
int ant = hull[(i+tam-1)%tam];
int prox = hull[(i+1)%tam];
if (!is_clockwise(hull[i], ant, prox)) {hull.erase(hull.begin()+i); --i;}
}
reverse(hull.begin(), hull.end());
for (int i = 0; i < hull.size(); i++)
{
int tam = hull.size();
int ant = hull[(i+tam-1)%tam];
int prox = hull[(i+1)%tam];
if (is_clockwise(hull[i], ant, prox)) {hull.erase(hull.begin()+i); --i;}
}
give_answer((int)hull.size());
}
컴파일 시 표준 에러 (stderr) 메시지
tri.cpp: In function 'void ordena(std::vector<int>&)':
tri.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for (int i = 1; i < v.size(); i++)
| ~~^~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < hull.size(); i++)
| ~~^~~~~~~~~~~~~
tri.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < hull.size(); i++)
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |