이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
ll ask(ll a,ll b,ll c){
return is_clockwise(a+1,b+1,c+1);
}
ll n;
ll P;
bool comp(ll a,ll b){
bool ans = ask(P,a,b);
return ans;
}
vi getHullGivenPoint(ll p, vi points){
auto it = find(all(points),p);
if(it!=points.end()) points.erase(it);
P = p;
sort(all(points),comp);
if(points.size()==0) return vi(1,p);
/*rep(i,0,points.size()){
cout<<points[i]<<" ";
}
cout<<endl;*/
vi hull;
hull.push_back(p);
hull.push_back(points[0]);
rep(i,1,points.size()){
assert(hull.size()>=2);
while(!ask(hull[hull.size()-2],hull[hull.size()-1],points[i])){
hull.pop_back();
assert(hull.size()>=2);
}
hull.push_back(points[i]);
}
return hull;
}
vi combineHulls(vi hull1,vi hull2){
ll a1,a2,b1,b2;
rep(w,0,2){
ll i1 = 0;
ll i2 = 0;
ll a = hull1.size();
ll b = hull2.size();
while(true){
if(!ask(hull1[i1],hull2[i2],hull2[(i2+1)%b])){
i2 = (i2+1)%b;
} else if(!ask(hull1[(i1+a-1)%a],hull1[i1],hull2[i2])){
i1 = (i1+a-1)%a;
} else break;
}
if(w==0) {
a1 = i1;
b1 = i2;
if(a1==0) a1 = a;
} else {
a2 = i2;
b2 = i1;
if(b2==0) b2 = b;
}
swap(hull1,hull2);
}
ll a = hull1.size();
ll b = hull2.size();
vi res;
rep(i,0,a+1){
if(i>=a2&&i<=a1) res.push_back(hull1[i%a]);
}
rep(i,0,b+1){
if(i>=b1&&i<=b2) res.push_back(hull2[i%b]);
}
return res;
}
int main(){
cin.sync_with_stdio(false);
n = get_n();
vi points(n);
rep(i,0,n) points[i] = i;
srand(5);
random_shuffle(all(points));
ll a = points[0];
ll b = points[1];
//cout<<a<<" "<<b<<endl;
vi points1;
vi points2;
rep(i,2,points.size()){
if(ask(a,b,points[i])){
points1.push_back(points[i]);
} else {
points2.push_back(points[i]);
}
}
/*cout<<"Points 1: "<<endl;
rep(i,0,points1.size()) cout<<points1[i]<<" ";
cout<<endl;
cout<<"Points 2: "<<endl;
rep(i,0,points2.size()) cout<<points2[i]<<" ";
cout<<endl;*/
vi hull1 = getHullGivenPoint(a,points1);
vi hull2 = getHullGivenPoint(b,points2);
/* cout<<"Hull 1: "<<endl;
rep(i,0,hull1.size()) cout<<hull1[i]<<" ";
cout<<endl;
cout<<"Hull 2: "<<endl;
rep(i,0,hull2.size()) cout<<hull2[i]<<" ";
cout<<endl;*/
vi hull;
if(hull1.size()==1) hull = getHullGivenPoint(hull1[0],points);
else if(hull2.size()==1) hull = getHullGivenPoint(hull2[0],points);
else hull = combineHulls(hull1,hull2);
/*cout<<"Hull: "<<endl;
rep(i,0,hull.size()) cout<<hull[i]<<" ";
cout<<endl;
*/
give_answer(hull.size());
}
# | 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... |