d796dcebe4 2019-08-11 kinaba: #include <iostream> d796dcebe4 2019-08-11 kinaba: #include <sstream> d796dcebe4 2019-08-11 kinaba: #include <iomanip> d796dcebe4 2019-08-11 kinaba: #include <vector> d796dcebe4 2019-08-11 kinaba: #include <string> d796dcebe4 2019-08-11 kinaba: #include <map> d796dcebe4 2019-08-11 kinaba: #include <set> d796dcebe4 2019-08-11 kinaba: #include <algorithm> d796dcebe4 2019-08-11 kinaba: #include <numeric> d796dcebe4 2019-08-11 kinaba: #include <iterator> d796dcebe4 2019-08-11 kinaba: #include <functional> d796dcebe4 2019-08-11 kinaba: #include <complex> d796dcebe4 2019-08-11 kinaba: #include <queue> d796dcebe4 2019-08-11 kinaba: #include <stack> d796dcebe4 2019-08-11 kinaba: #include <cmath> d796dcebe4 2019-08-11 kinaba: #include <cassert> d796dcebe4 2019-08-11 kinaba: #include <tuple> d796dcebe4 2019-08-11 kinaba: using namespace std; d796dcebe4 2019-08-11 kinaba: typedef long long LL; d796dcebe4 2019-08-11 kinaba: typedef complex<double> CMP; d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: class InsidePoints { public: d796dcebe4 2019-08-11 kinaba: vector <int> construct(vector <int> x, vector <int> y) d796dcebe4 2019-08-11 kinaba: { d796dcebe4 2019-08-11 kinaba: map<int, set<int>> x2y; d796dcebe4 2019-08-11 kinaba: for (int i = 0; i < x.size(); ++i) d796dcebe4 2019-08-11 kinaba: x2y[x[i]].insert(y[i]); d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: vector<pair<int,int>> left; d796dcebe4 2019-08-11 kinaba: vector<pair<int, int>> upper; d796dcebe4 2019-08-11 kinaba: vector<pair<int, int>> lower; d796dcebe4 2019-08-11 kinaba: vector<pair<int, int>> right; d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: int prevx = -99999999; d796dcebe4 2019-08-11 kinaba: int prevy = -99999999; d796dcebe4 2019-08-11 kinaba: for (auto it : x2y) { d796dcebe4 2019-08-11 kinaba: int x = it.first; d796dcebe4 2019-08-11 kinaba: set<int> ys = it.second; d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: if (prevx == -99999999) { d796dcebe4 2019-08-11 kinaba: upper.emplace_back(x, *ys.rbegin() + 1); d796dcebe4 2019-08-11 kinaba: lower.emplace_back(x, *ys.begin() - 1); d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: for (int yy = *ys.rbegin(); yy >= *ys.begin(); --yy) d796dcebe4 2019-08-11 kinaba: left.emplace_back(ys.count(yy) ? x - 1 : x, yy); d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: else { d796dcebe4 2019-08-11 kinaba: for (int xt = prevx + 1; xt < x; ++xt) { d796dcebe4 2019-08-11 kinaba: upper.emplace_back(xt, prevy+1); d796dcebe4 2019-08-11 kinaba: lower.emplace_back(xt, prevy); d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: upper.emplace_back(x, *ys.rbegin() + 1); d796dcebe4 2019-08-11 kinaba: int id = -1; d796dcebe4 2019-08-11 kinaba: for (int yy = *ys.rbegin(); yy >= *ys.begin(); --yy) d796dcebe4 2019-08-11 kinaba: if (ys.count(yy) == 0) { d796dcebe4 2019-08-11 kinaba: lower.emplace_back(x, yy); d796dcebe4 2019-08-11 kinaba: lower.emplace_back(x-1, id--); d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: lower.emplace_back(x, *ys.begin() - 1); d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: if (x2y.rbegin()->first == x) { d796dcebe4 2019-08-11 kinaba: for (int yy = *ys.rbegin(); yy >= *ys.begin(); --yy) d796dcebe4 2019-08-11 kinaba: right.emplace_back(ys.count(yy) ? x + 1 : x, yy); d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: prevx = x; d796dcebe4 2019-08-11 kinaba: prevy = *ys.rbegin(); d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: vector<pair<int,int>> ans; d796dcebe4 2019-08-11 kinaba: ans.insert(ans.end(), left.begin(), left.end()); d796dcebe4 2019-08-11 kinaba: ans.insert(ans.end(), lower.begin(), lower.end()); d796dcebe4 2019-08-11 kinaba: ans.insert(ans.end(), right.rbegin(), right.rend()); d796dcebe4 2019-08-11 kinaba: ans.insert(ans.end(), upper.rbegin(), upper.rend()); d796dcebe4 2019-08-11 kinaba: vector<int> flat_ans; d796dcebe4 2019-08-11 kinaba: for (auto xy : ans) { d796dcebe4 2019-08-11 kinaba: flat_ans.push_back(xy.first); d796dcebe4 2019-08-11 kinaba: flat_ans.push_back(xy.second); d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: return flat_ans; d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: }; d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: // BEGIN CUT HERE d796dcebe4 2019-08-11 kinaba: #include <ctime> d796dcebe4 2019-08-11 kinaba: double start_time; string timer() d796dcebe4 2019-08-11 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d796dcebe4 2019-08-11 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d796dcebe4 2019-08-11 kinaba: { os << "{ "; d796dcebe4 2019-08-11 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d796dcebe4 2019-08-11 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d796dcebe4 2019-08-11 kinaba: void verify_case(const vector <int>& Expected, const vector <int>& Received) { d796dcebe4 2019-08-11 kinaba: bool ok = (Expected == Received); d796dcebe4 2019-08-11 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d796dcebe4 2019-08-11 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } d796dcebe4 2019-08-11 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d796dcebe4 2019-08-11 kinaba: #define END verify_case(_, InsidePoints().construct(x, y));} d796dcebe4 2019-08-11 kinaba: int main(){ d796dcebe4 2019-08-11 kinaba: d796dcebe4 2019-08-11 kinaba: CASE(0) d796dcebe4 2019-08-11 kinaba: int x_[] = {4}; d796dcebe4 2019-08-11 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d796dcebe4 2019-08-11 kinaba: int y_[] = {7}; d796dcebe4 2019-08-11 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); d796dcebe4 2019-08-11 kinaba: int __[] = {3, 7, 4, 8, 5, 6 }; d796dcebe4 2019-08-11 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); d796dcebe4 2019-08-11 kinaba: END d796dcebe4 2019-08-11 kinaba: CASE(1) d796dcebe4 2019-08-11 kinaba: int x_[] = {4, 6}; d796dcebe4 2019-08-11 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d796dcebe4 2019-08-11 kinaba: int y_[] = {7, 7}; d796dcebe4 2019-08-11 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); d796dcebe4 2019-08-11 kinaba: int __[] = {3, 6, 7, 6, 7, 8, 5, 7, 3, 8 }; d796dcebe4 2019-08-11 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); d796dcebe4 2019-08-11 kinaba: END d796dcebe4 2019-08-11 kinaba: CASE(2) d796dcebe4 2019-08-11 kinaba: int x_[] = {1, 1, 2, 2}; d796dcebe4 2019-08-11 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d796dcebe4 2019-08-11 kinaba: int y_[] = {1, 2, 1, 2}; d796dcebe4 2019-08-11 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); d796dcebe4 2019-08-11 kinaba: int __[] = {0, 0, 3, 0, 3, 3, 0, 3 }; d796dcebe4 2019-08-11 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); d796dcebe4 2019-08-11 kinaba: END d796dcebe4 2019-08-11 kinaba: CASE(3) d796dcebe4 2019-08-11 kinaba: int x_[] = {1, 2, 3, 3, 3, 3, 5, 4}; d796dcebe4 2019-08-11 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d796dcebe4 2019-08-11 kinaba: int y_[] = {3, 3, 1, 5, 2, 4, 3, 3}; d796dcebe4 2019-08-11 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); d796dcebe4 2019-08-11 kinaba: int __[] = {0, 2, 2, 2, 2, 0, 4, 0, 4, 2, 6, 2, 6, 4, 4, 4, 4, 6, 2, 6, 2, 4, 3, 3, 1, 4, 0, 4 }; d796dcebe4 2019-08-11 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); d796dcebe4 2019-08-11 kinaba: END d796dcebe4 2019-08-11 kinaba: /* d796dcebe4 2019-08-11 kinaba: CASE(4) d796dcebe4 2019-08-11 kinaba: int x_[] = ; d796dcebe4 2019-08-11 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d796dcebe4 2019-08-11 kinaba: int y_[] = ; d796dcebe4 2019-08-11 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); d796dcebe4 2019-08-11 kinaba: int __[] = ; d796dcebe4 2019-08-11 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); d796dcebe4 2019-08-11 kinaba: END d796dcebe4 2019-08-11 kinaba: CASE(5) d796dcebe4 2019-08-11 kinaba: int x_[] = ; d796dcebe4 2019-08-11 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); d796dcebe4 2019-08-11 kinaba: int y_[] = ; d796dcebe4 2019-08-11 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); d796dcebe4 2019-08-11 kinaba: int __[] = ; d796dcebe4 2019-08-11 kinaba: vector <int> _(__, __+sizeof(__)/sizeof(*__)); d796dcebe4 2019-08-11 kinaba: END d796dcebe4 2019-08-11 kinaba: */ d796dcebe4 2019-08-11 kinaba: } d796dcebe4 2019-08-11 kinaba: // END CUT HERE