fork download
copy 
  1. /**
  2.     Template by Akikaze (秋風) - formerly proptit_4t41.
  3.     Code written by a random fan of momocashew and Chiho.
  4.     
  5.     H△G x Mili - November 27th, 2013
  6.     Mag Mell (Mili) - Sep 17th, 2014
  7.     H△G x Mili Vol.2 - May 9th, 2015
  8.     Miracle Milk (Mili) - Oct 12th, 2016
  9.     青色フィルム (H△G) - February 14th, 2018
  10.     Millennium Mother (Mili) - April 25th, 2018
  11. **/
  12.  
  13. /** -----PRAGMA----- **/
  14. #pragma comment(linker, "/stack:200000000")
  15. #pragma GCC optimize("Ofast")
  16. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  17.  
  18. #include <bits/stdc++.h>
  19. using namespace std;
  20.  
  21. /** -----BASIC MACROES----- **/
  22. #define endl '\n'
  23. #define i64 long long
  24. #define ld long double
  25. #define pub push_back
  26. #define mp make_pair
  27. #define fi first
  28. #define se second
  29. const long long MOD = 1000000007LL, INF = 1e9, LINF = 1e18;
  30. const long double PI = 3.141592653589793116, EPS = 1e-9, GOLD = ((1+sqrt(5))/2);
  31. typedef vector<i64> vi;
  32. typedef vector<ld> vd;
  33. typedef vector<string> vs;
  34. typedef vector<bool> vb;
  35. typedef pair<i64, i64> pii;
  36. typedef pair<i64, pii> pip;
  37. typedef pair<pii, i64> ppi;
  38.  
  39. /** -----BIT CONTROLS----- **/
  40. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  41. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  42. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  43. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  44.  
  45. /** -----IDEAS/ALGORITHMS-----
  46.  
  47.     -------------------------- **/
  48.  
  49. /** -----CUSTOM TYPEDEFS/DEFINES----- **/
  50. i64 cmp1(double A, double B) {
  51.     if (A - B < -EPS) return -1;// A < B
  52.     if (A - B > EPS) return 1;// A > B
  53.     return 0;// A = B
  54. }
  55.  
  56. struct point {
  57.     double x, y;
  58.     bool operator < (const point& that) const {
  59.         if(cmp1(x, that.x) != 0) return cmp1(x, that.x) < 0;
  60.         return cmp1(y, that.y) < 0;
  61.     }
  62. };
  63. bool cmp(point a, point b) {
  64.     return a.x < b.x || a.x == b.x && a.y < b.y;
  65. }
  66. bool cw(point a, point b, point c) {
  67.     return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
  68. }
  69. bool ccw(point a, point b, point c) {
  70.     return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
  71. }
  72. void convex_hull(vector<point> &a) {
  73.     if (a.size() == 1)
  74.         return;
  75.     sort(a.begin(), a.end(), &cmp);
  76.     point p1 = a[0], p2 = a.back();
  77.     vector<point> up, down;
  78.     up.push_back(p1);
  79.     down.push_back(p1);
  80.     for (size_t i=1; i<a.size(); ++i) {
  81.         if (i==a.size()-1 || cw (p1, a[i], p2)) {
  82.             while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
  83.                 up.pop_back();
  84.             up.push_back(a[i]);
  85.         }
  86.         if (i==a.size()-1 || ccw (p1, a[i], p2)) {
  87.             while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
  88.                 down.pop_back();
  89.             down.push_back(a[i]);
  90.         }
  91.     }
  92.     a.clear();
  93.     for (size_t i=0; i<up.size(); ++i)
  94.         a.push_back(up[i]);
  95.     for (size_t i=down.size()-2; i>0; --i)
  96.         a.push_back(down[i]);
  97. }
  98.  
  99. /** -----GLOBAL VARIABLES----- **/
  100.  
  101.  
  102. /** -----EXTENSIVE FUNCTIONS----- **/
  103.  
  104.  
  105. /** -----COMPULSORY FUNCTIONS----- **/
  106. void VarInput() {
  107.     ios_base::sync_with_stdio(0); cin.tie(NULL);
  108.  
  109. }
  110.  
  111. void ProSolve() {
  112.     i64 n; cin >> n;
  113.     while (n != 0) {
  114.         vector<point> a; map<point, i64> Map;
  115.         for (i64 i=0; i<n; i++) {
  116.             point pts; cin >> pts.x >> pts.y;
  117.             if (!Map[pts]) a.pub(pts); Map[pts]++;
  118.         }
  119.         convex_hull(a);
  120.         cout << a.size() << endl;
  121.         for (i64 i=a.size()-1; i>=0; i--) cout << a[i].x << " " << a[i].y << endl;
  122.         cin >> n;
  123.     }
  124. }
  125.  
  126. /** -----MAIN FUNCTION----- **/
  127. int main() {
  128.             #ifdef Akikaze
  129.             //freopen("FILE.INP", "r", stdin);
  130.             //freopen("FILE.OUT", "w", stdout);
  131.             #endif
  132.     VarInput();
  133.             #ifdef Akikaze
  134.             auto TIME1 = chrono::steady_clock::now();
  135.             #endif
  136.     ProSolve();
  137.             #ifdef Akikaze
  138.             auto TIME2 = chrono::steady_clock::now();
  139.             auto DIFF = TIME2 - TIME1;
  140.             cout << "\n\nTime elapsed: " << chrono::duration<double>(DIFF).count() << " seconds.";
  141.             #endif
  142.     return 0;
  143. }
  144.  
  145. /**
  146. OOO###$-^`^^.--~~~-.~~~~~-.^~~~~__~:++;+;~^^^^-!%eiiio?O##?i==e####!iiiii:.^^
  147. ##OO##$-^`^^.-~~~~~..~~~~~.^~~~~__~:+;;;;~^``^-*!!**o*e$##!=++*O###e=====:.^^
  148. ##OOOO$-^```.~~~~~~..~~~~~.^~~~~-_~:+;;;;~```^-e!eee**e$##!+;;oO###*====+_^^^
  149. ###OOO$_^```^~~~~~~..~~~~~.^.~~~-_~:+;;;;.```^-?!ee***e$##e;;;oO###*+++++_^`^
  150. ######O_^```^~~~~~~.......^^...~--~:;::::.````~ee***ooe$##e;::iO##Oo+++++-^``
  151. ####O$%_^```^.^^^^^^^^^^^^^^^^^^....~~~~~.````~;;:::::;=ii+_-_;o***+:::::-^`^
  152. O$$O$%e-^```^^.~....^.....^^.....^^.^^^^^^````^......^....................^``
  153. i++iiee-^```^.-;__:_.-:__:~._:-__..-----.^````^~-~~-~.~-~~-..~~~~..~~~~~.^^``
  154. :::;;i=-^```^.-;_-;_._;__;-.:;_:;~~::_:_.^````^-:__;-._;_:;~~___;-.__-::.^^``
  155. +;;;=i;~^````^-_--_-.-_--:~._:-__.~__-__.^````^~_--:-.-_-::.~_--:-.__-__.^^``
  156. ii=io*+~^````^-:--:-.-:__:-.__-__.._--_-.^````^~_--_~.---__.~_--:~.__-__.^```
  157. ee*e!!o-^````^-:_-:_._;__;-._:-::.~:_-;_.`````^-;__:-._:-::.~;__;-._:_;:.^```
  158. ??????e_^````^~~~~-~.~-~~-~.--~--.._--_-.^````^~_--_~.-_-__.~:--:~.__-:_.^```
  159. %%%??%!;^````^^^^^^^^^^^^^^^^^^^^^^^^...^^````^......^.....^......^.....^^```
  160. %%%%?%%o~`````````````````````````````^``````^^``^^^^^^^``^^^^^^^^^^^^^^^^```
  161. $$$$%%$!:^``````````````````````````````````^^```````````````````````````````
  162. #OOOOO$%o~````````````````````````````^^^^^..^`^^^..^``````````````````^^^^^^
  163. #####OO$!_^``^^^^^`^...^^``````````._+++++-~-.^.^..-.^````````````````^..~--:
  164. O######O%:...-____-_::_-~~~~-~.~~~_=ioo*eo===;_~.~~--~^^^^^^^^^^^^^^^^~--__::
  165. OOOOO##!:~^^.;!!?????o;__++===o*i:;+ii*!**oooi==;:_--:_:+=iii====;:;;__:+;__:
  166. OO%%$O#e~^^^^:!!$OOO?e=:__;+::_*=ii===oo**e***o*ooi;_--:=?%!!!!eo;:+;__;++;:;
  167. #O%?%$OO+.^`^:?%%##$i;::::_____oe!!?e*==oo*e**ee!?**+-_:_=oe!ee?=;;+;;;++::+=
  168. ##OO$%$O%_..~+??!%O?+;______:_=!?!$$?%!eo*****?!$!?!e+;:_:;o*o*!i;:;;+=+:_:;+
  169. #OO$?!?%$eiio*ooi==+::_:__;::;!%$$O$$$$%!e***!!$!%O$!oi:_;;ooiio*+;==+i+;+=ii
  170. $$?e*o*e!!!*o=;::;:_-__:::-::o$OOOOO#OO$$%!!ee%?O#$!!o+;::+i=+++=;++;+=+=i==o
  171. %?!*i=ioooo=+;:_:+=:__-___-_:%O#OOO###OOO%%%$$$OO$?%%=-_::_::;::::;;::::++++*
  172. OO%?*+;=o!e*o=+;;==:__:__--_iOO#######O#OOO##OO$$%$O?+_.:__;;;--;=i=++===++o!
  173. #O!i+;;:;+;:;+==o=:--_::::__?###O############O$OO#OO*+:.~__;=;--e$eo!!o*oiii=
  174. O?*=;:;;:_~~-~-_;__--_;:_::;O###############OO###OO!=;_-~-__i+__!O*+;:+ii=i_.
  175. ??!*=+=;;_-~~~-_:;+;_;+:_;;*##############&######O?*+:__----____ie=;_;+=+::.^
  176. e$e!*oi;:__--_:;::;;::+;:;i%#############&&######$!i;:_____-:;__=;-_::_:_~-~^
  177. *O?!ooi+;:_~-_---_;;::=+_;oO#####&####&#&&&#####?o+;:____;:__:-:+_--::__-.^^^
  178. *#Oe++;;__:~_;__:;;;+:+i;;o##########&##&&&&&&#%=;;:__;+;=;_-~~_--__+;:::.^^`
  179. eO$o+;::_;=+i=++;:-__;io;:*#########&##&##&&&&#e;::::=*%!o=:--:__::;++;+=:~^^
  180. eO%=;+===*e?%*=;:__:;+o!+_?#####OO####&#O#&&&#$i:::+o*=oo=::__;:_-+=+:+;_:_.^
  181. e$%=+oe*o?$?oo;-~~_:;o*e*e$#####OO######OO###O!=:_:=?%%*i+;;_--:+;o**;o=_~..^
  182. e$%e**!*?%!;-_i+-~_++**oe?$O###OO####&&##%$#O%*;:___i?$o+:;_-~_oiii=eieo=;-^^
  183. !$%!e!ee!?i++_:;+;===o*o=$####OO##&&&&&%O??$%?o;__-~-==_:_;=:;++i++io!$!+:-^`
  184. !%?*o!!ii+_==::;i=;e!*e*?O######&&&&&#&%??!?%?i;:__-~-----;e=:+====*!*!%;~.~^
  185. e%?*ioi*!++*?oo=e*;ooieo?O###O#&&&&&&&&%!!e??e=;;;;:_--_~:;=__+;;:;e!*+!i.^~.
  186. e%?eoi+o***e!e%!$%ii****%O#####&&&&&&&&Oeeee!o+++;+=+_-:~:;_-::_;;;oi;_=i~^^^
  187. !?!!??*=ie?ooe?oo=_-:i*!O#####&&&&&&&&&##$e*o=;;++=++:;_:;i;+;+io+;ii;~_;;_:;
  188. !ee?$%i=o!i+=*!ei-_::;;?O####&&&&&&&&&&##$ei=+;;+++=+;oi*=;-i*=**++oi:~~_;;=o
  189. !?!%$?=o?%o*%e!%=_+==++?OO###&&&&&&&&&&#O$!i=+;;++==i+oe=:+:??oo*===+;-.~_+*!
  190. !%?%O!i?#O###$%$!e!*=+*$O###&&&&&&&&&&&#$$!o=++++==ii=;io+i*%!oooi==i::~~~_!%
  191. e??%$?=i%###Oo*%$!o*ee?$####&&&&&&&&&&&#$%?*i=====iooeoo==oeeooo+!?!oo=:___*$
  192. e?%%%?==!###?=e$!o=o%$$O###&&&&&&&&&&&&#$??eo====ioo!?*i+=oi=++o!eeoi=~:;;:+!
  193. e?%$$%o*$###O!%?eo*e$%$####&&&&&&&&&&&&O???e*i==iio*o*o+====*!+o$!oi=_^.-:===
  194. ?%$##O%%O####OO%?i*%$$O###&&&&&&&&&&&&#$!??!eoiiio**iiiio*ooe$*?#!eii;-~_+oi=
  195. %%$#&#OO#######O!!%?$O###&&&&&&&&&&&&&O?e!?!e*oio*ooi+++o!e!e$?$O?!+i****ee*o
  196. ??$###OOOOO####$!$$%$?###&&&&&&&&&&&&&%!*e?!e*iiioooi;:=ie?%%$O!%e*+o?%?*ooii
  197. e%O#&#O$OOO$O##O$OO$!?##&&#&&&&&&&&&&O?**e!!e?%oiiioo-_:+??$%%?=o!o+:+i+:_---
  198. ?$O###OOO#$?%O##O$OO$O##&#&&&&&&&&###%e*o*ee!%**%e:i=.:=*??%?!?eoei:-_:_~~~..
  199. O$$OO##O##$!e%OO$$OO$##&###&&##&####%!*oo*ee%%%%$?i*e=o;oe!%?ie!o*=:___----~~
  200. #$%?!?O#O%%!e!%$%!!$O##&##&&####O##%eoiio**??!%$#O%!!*ei;=;i?e??e*i=++;;;++::
  201. #Oe-.:$#$%?????!!o=?##&&#&&###O$##!i+==io**?%?$$O#%??!=i=+:-o%O%!o!%?!e!!?!ee
  202. O?-``:%$$%%%??%?!=i$O#&##&&#&O?$%=--_;+=o*?%??O%OOO?e?iioi!o*%O%?o?%%%$$$$$$$
  203. ?_``~o!???!!!!!ee*!OO#&##&##%??+.``^~_;+i*O$OOO$$OO%%?e*ie%%e%O?eo?e!$O$?!%$$
  204. :` .+e!!eeeeeee**!!O#&#&&&#$?+.     `._:+=o*$OOO%%$%$$?*;o%?*!?*=e$$$###$$OOO
  205. ^ ^::i!e*o****e**!!$##&&&#O?-^       ``~_:_*$OOOOOOOO?!!;ie!io!*i?O##########
  206. ``_o;=*ooooo*****ee$#&&&&#?.`         ``^~-_%$OO#OOOOe*$?*o!io!=i!%OOOOO$$%$$
  207. ~_i*+oooooooo**o*ee$##&&##-.           ```.~*$$$OOOOO?o?$!o*i*o+o!%%?%%%????%
  208. i;=i+iooooiioo**ee!$#&&&#e^             ``^^:$?$O$%OO$e!$?=+io==ee???????!!!?
  209. ?;_+=i=iooiioo**e!!O&&&&#:`              `^^^?OOO$?$OO%e?ei+i**oo*eeeee******
  210. ?*;;=iiiiiiioio**!!O&&&&?^ `       ```   ``^^:OO$O$OO$O$?i++io*==iooooooooooo
  211. ?*++=iiiiooioi**e!?O&&&&+```    ~=^-____~```^^*OOO##O$%$?o*!i=iiiiiiiiiiiii==
  212. ?o+=oiioooioo****!%#&&&O.`^`    -=_---_;+;^``^.%O####O$!!!?!i=i========++++++
  213. !i=ioooiooo**e!e!?%#&&&*`^``` ``    `    .:.```;O####OO?!??!==i==++++;;;;;;;;
  214. *=io*oooi*e!!???%$O#&&#-^.`````` ```..^^`` .^```e##OO$$%?!*o+===+;;:::::::___
  215. oooeeee**!!%%%?%$O##&&?^.^`````^  `~.^^^`^.`````.$OOOO$**?!ooi=+;::_____-----
  216. ee*eee!?%%%$$$%$OO#&&&+^.^`````^^`~~.^.^``.~^^```+OO#O$oe%*ioo++;::___:_-----
  217. e*o**e?%%$%$OOO$$O#&&#~^.^^^^``^.~-....^``.~.~````?##O$e?%*+ii++;;::::;::____
  218. eooo*%OOO#####OO$O#&&$^^.^^^``^^~-~....^^`^~~~^```_O#O$?%$$io=;;;;;;;;;;;;;::
  219. *oo*!O#######O$%$O#&&e^..^^^`^^^.~.....^^`^.~~~^```*#O$%%O#$e;:;;;;:::_::____
  220. *oe??%$%$%?%%%??%$##&i`..^^^^^^^.~.~...^``^.~~-.```.OO%%$O##!;_;+;:__-~--~~~~
  221. *i*e*eeee!!!!e!!%%#O#+^^.....^^^.~.~~..^``^^.~-~^```+%$%?$##!;_;+;;:_~~-_-~~~
  222. *ioe*ee*!!e!!e!!%$O?#+^^...~.^^^.~~~~.^```^^.~~-~```.%$?!$OO!;_;++;:_-~---~~~
  223. o=ie*e**!e*ee*e%$##?#+`^..~~^^^^.~~...^```^^^.~--^```!%!%%OO?+:;++;;:_-~--~~~
  224. o==**e*e!e*e?!oeO#O$&=``^.~~^^^.~~~...^` ``^^.~~~~```o%?%!?%?=::;;;;:-~~~~~~~
  225. *i=*!e*eeeeee?%%O$$##=^`^.~.^^..~~~..``````^^^~~~~^``=$?%%%$$?i;++++;-~--~~~~
  226. !oie!!e!!**eoo?%$####=_`^.~^....~~....~--_~.~....~~``~%*i!?!**i=====+:-::-~~~
  227. !*ie!**!!***ooe%%#&&&i:.^^.^^..^.~~~__--:;;..~..~~~.``ee=***=iooiii==+++:-~~~
  228. $?eeeoo!*ooi=i**io#&&e_~^^.^^..~::::__~-:::.-~-~+.~.^`iO$$$$???!!i=+++==;--~~
  229. $%??*o*eo+oooi*o;i$O&$--^^.^^._::__:____::_.~--~*~..^^+####OO?%%?+;::;;;:----
  230. !???!!!*oieo==*=;;+=e#:-.^^^.:___-_:__::__-~-.~~oi.^..;######$??e:______-----
  231. ??%?!e!eeee*ii*=;+=++*+_.^^.:__--------_-_.~-~--;?-..~+O######$%!:___--------
  232. !!??ee?!ee*oii+;++i+;+i:-.._:-_--_-__--_--^~~.~-.**..-iO##O####$?:_______----
  233. e!%?eee*o*o====+++=+;+i:;~.;_-_~~--------~^~-~.-.-!:~-*#OOO##O#$!+;;;:;;;:::_
  234. ee??!eiii*oi==*=+;==+=o=;:~+_:_.~--~~~~~~..~~~.-~.i*.-*OOO#O##OOo=ii======+++
  235. !**e!!oii*oi=o*+;;====oi;+-+::-~--~~~~~~~^.~~~.-~-~!:_eOO######Oe=iii=====+++
  236. ?!**ee*oo*ii=oo;:;==+=*o+;:=;;_~~~~~~~~~~^~~~~.-~_~o=_!#OO#####O$o======+++++
  237. ?*ii!eoooi===oi;;:+++=**o++=;;_.~~~~~....^.~~~.~~:_;o_?#OOOO###O%i+++++++++;;
  238. !iii!oiooi==ioi===iiio*oi=+o=;_~~~~~~...^.~~~~.~~:_-o_%OOOO###OO%i;;;;;;;;;;;
  239. !**e!ooo**iio*o+;+ii==iooo==o;:.~~~~~...^..~~~..~_:_=_$O#OOO##OO$e;;;::;;;:::
  240. e**e*i=ioii=o!*i++===+ioi*i=o+:~~~~~~...`..~~~..~:;;+:OO#OOOOO##O%+::::::::__
  241. ee*!oi=ioiii*!!o++==i=oooooi==;~~~~~~...^...~...-;;+;+$$O####O#OO$+::________
  242. *oe*=iiooi=i*e*i==oi=+=ioi=ii+;~~~~~...^^...~~..-;+*;*OOO#######$%=::________
  243. io!i+io**i=ie*i===ii==oe!ee?i=;-~~~....^^......._;e*;%OOO#####O#O$*;:;:______
  244. =ie*ii=ii==ie*=++;=i=i**ee!?!i=_~~~....^........:;O*i$##OOO#O#O##O$+:;::_____
  245. iiooii=i==io**=;;;====io*eeeeoi:-~~....^.....~..;=#!oOO##OOOO###O#Oi;;:__---_
  246. **/
  247.  
  248. // Tribute to a friend I owe countless. Thanks, TN.
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
3
0 0
10 0
0 10
5
41 -6
-24 -74
-51 -6
73 17
-30 -34
2
50 50
50 50
0
stdout
copy 
3
10 0
0 10
0 0
3
-24 -74
73 17
-51 -6
1
50 50
https://ideone.com/s4OAeI
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!