Language: C++

 
AIZU ONLINE JUDGE




PAGETOP

 

???????????????

 

??????????????°

 

???????????????

 

???????????????

 

?????????

 

 



































































































 
?????°??¢??????
 
??????????¨????
 









??\??¬???   ??±??? 

My Status ?????????????????????     HOME- 





Notes 
 




#1056742 

Solution for CGL_4_A: Convex Hull by ne220081

?????????????????? ??????????????? ???????????±??????  
    ??¢?????????: public     ?????§??°: 24     





00.25 sec    5756 KB    93 lines     2144 bytes    2014-08-27 20:24 




?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define X real()
#define Y imag()
#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]
const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return imag(a) != imag(b) ? imag(a) < imag(b) : real(a) < real(b);
  }
}
 
//??????
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
 
//??????
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}
 
//??? (??????)
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
 
int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}
 
//????§???¢
typedef vector<P> G;
 
G convex_hull(G &ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  G ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
  ch.resize(k-1);
  return ch;
}
 
int main() {
  int N; cin >>N;
  G g(N);
  REP(i, N){
    int x, y; cin >>x >>y;
    g[i] = P(x, y);
  }
  G ans = convex_hull(g);
  cout <<ans.size() <<endl;
  REP(i, ans.size()) cout <<ans[i].X <<" " <<ans[i].Y <<endl;
  return 0;
}
 

 
Compile Error Logs: 

You are not authorized to see the message. 
 
 
??????????????? 
Judge: 24/24  C++  CPU: 00.25 sec  Memory: 5756 KB  Length: 2144 B  2014-08-27 20:24  2014-08-27 20:24  
???????????±????????????????????? 
Case # Verdict CPU Time Memory In Out Case Name 
 Case #1: : Accepted  00.00 sec 1284 KB    
 Case #2: : Accepted  00.00 sec 1264 KB    
 Case #3: : Accepted  00.00 sec 1268 KB    
 Case #4: : Accepted  00.00 sec 1268 KB    
 Case #5: : Accepted  00.00 sec 1284 KB    
 Case #6: : Accepted  00.00 sec 1280 KB    
 Case #7: : Accepted  00.00 sec 1284 KB    
 Case #8: : Accepted  00.00 sec 1284 KB    
 Case #9: : Accepted  00.00 sec 1284 KB    
 Case #10: : Accepted  00.00 sec 1280 KB    
 Case #11: : Accepted  00.00 sec 1276 KB    
 Case #12: : Accepted  00.00 sec 1280 KB    
 Case #13: : Accepted  00.00 sec 1284 KB    
 Case #14: : Accepted  00.03 sec 3380 KB    
 Case #15: : Accepted  00.06 sec 5756 KB    
 Case #16: : Accepted  00.01 sec 2060 KB    
 Case #17: : Accepted  00.02 sec 2852 KB    
 Case #18: : Accepted  00.04 sec 3644 KB    
 Case #19: : Accepted  00.06 sec 5756 KB    
 Case #20: : Accepted  00.00 sec 1288 KB    
 Case #21: : Accepted  00.03 sec 1796 KB    
 Case #22: : Accepted  00.00 sec 1424 KB    
 Case #23: : Accepted  00.25 sec 4964 KB    
 Case #24: : Accepted  00.07 sec 2588 KB    



 < prev | 1 /  24 | next >      : Accepted        00.00 sec        1284 KB 

 

Judge Input #1 (  | )  Judge Output #1 (  | ) 


  

 

Comments 
 

 ??\????????§?????? 

 
Categories 
 



 
Free Tags 
 



 



 
   










 

        

 

 
Aizu Online Judge
 follow us on Twitter






About us
 
ContactSystem InfoThe University of Aizu


Tools
 
WEB Board ToolsVirtual ArenaAPI ReferenceTutorial


Links
 
ACM/ICPCACM/ICPC Asia JapanACM-ICPC OB/OG Alumni GroupPC KoshienJOI

AtCoderTopCoderCodeForces

Uva Online judgesACM-ICPC Live ArchivePKU JudgeOnline 

Aizu IT Arena 


Best viewed using Firefox, Google Chrome

Aizu Online Judge Version 1.0 ?? 2004 - 2015 AIZU Competitive Programming Club (ICPCPC), Database Systems Lab. University of Aizu

 

Compiler output:
a.cc:15:15: error: extended character ° is not valid in an identifier
   15 | ??????????????°
      |               ^
a.cc:132:6: error: extended character ° is not valid in an identifier
  132 | ?????°??¢??????
      |      ^
a.cc:132:9: error: extended character ¢ is not valid in an identifier
  132 | ?????°??¢??????
      |         ^
a.cc:145:3: error: stray '\' in program
  145 | ??\??¬???   ??±???
      |   ^
a.cc:145:6: error: extended character ¬ is not valid in an identifier
  145 | ??\??¬???   ??±???
      |      ^
a.cc:145:15: error: extended character ± is not valid in an identifier
  145 | ??\??¬???   ??±???
      |               ^
a.cc:1056745:47: error: extended character ± is not valid in an identifier
a.cc:1056746:7: error: extended character ¢ is not valid in an identifier
a.cc:1056746:36: error: extended character § is not valid in an identifier
a.cc:1056746:40: error: extended character ° is not valid in an identifier
a.cc:1056752:57: error: invalid digit "8" in octal constant
a.cc:1056951:74: error: invalid digit "8" in octal constant
a.cc:1056951:92: error: invalid digit "8" in octal constant
a.cc:1056952:12: error: extended character ± is not valid in an identifier
a.cc:1056953:6: error: stray '#' in program
a.cc:1056954:7: error: stray '#' in program
a.cc:1056955:7: error: stray '#' in program
a.cc:1056956:7: error: stray '#' in program
a.cc:1056957:7: error: stray '#' in program
a.cc:1056958:7: error: stray '#' in program
a.cc:1056959:7: error: stray '#' in program
a.cc:1056960:7: error: stray '#' in program
a.cc:1056961:7: error: stray '#' in program
a.cc:1056962:7: error: stray '#' in program
a.cc:1056963:7: error: stray '#' in program
a.cc:1056964:7: error: stray '#' in program
a.cc:1056965:7: error: stray '#' in program
a.cc:1056966:7: error: stray '#' in program
a.cc:1056967:7: error: stray '#' in program
a.cc:1056968:7: error: stray '#' in program
a.cc:1056969:7: error: stray '#' in program
a.cc:1056970:7: error: stray '#' in program
a.cc:1056971:7: error: stray '#' in program
a.cc:1056972:7: error: stray '#' in program
a.cc:1056973:7: error: stray '#' in program
a.cc:1056974:7: error: stray '#' in program
a.cc:1056975:7: error: stray '#' in program
a.cc:1056976:7: error: stray '#' in program
a.cc:1056977:7: error: stray '#' in program
a.cc:1056985:13: error: stray '#' in program
a.cc:1056985:37: error: stray '#' in program
a.cc:1056995:4: error: stray '\' in program
a.cc:1056995:13: error: extended character § is not valid in an identifier
a.cc:2:1: error: 'AIZU' does not name a type
    2 | AIZU ONLINE JUDGE
      | ^~~~
In file included from /usr/include/c++/14/iosfwd:42,
                 from /usr/include/c++/14/ios:40,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1056851:
/usr/include/c++/14/bits/postypes.h:68:11: error: 'ptrdiff_t' does not name a type
   68 |   typedef ptrdiff_t     streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/14/bits/postypes.h:41:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/14/bits/exception_ptr.h:38,
                 from /usr/include/c++/14/exception:166,
                 from /usr/include/c++/14/ios:41:
/usr/include/c++/14/new:131:26: error: declaration of 'operator new' as non-function
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:131:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/14/cwchar:44,
                 from /usr/include/c++/14/bits/postypes.h:40:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:132:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  132 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:133:26: error: declaration of 'operator new []' as non-function
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:133:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:134:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  134 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:140:29: error: 'std::size_t' has not been declared
  140 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                             ^~~
/usr/include/c++/14/new:142:31: error: 'std::size_t' has not been declared
  142 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                               ^~~
/usr/include/c++/14/new:145:26: error: declaration of 'operator new' as non-function
  145 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/14/new:145:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  145 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:145:52: error: expected primary-expression before 'const'
  145 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/14/new:147:26: error: declaration of 'operator new []' as non-function
  147 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/14/new:147:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  147 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:147:54: error: expected primary-expression before 'const'
  147 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                      ^~~~~
/usr/include/c++/14/new:154:26: error: declaration of 'operator new' as non-function
  154 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                          ^~~~~~~~
/usr/include/c++/14/new:154:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  154 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:154:68: error: expected primary-expression before ')' token
  154 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                                                                    ^
/usr/include/c++/14/new:155:73: error: attributes after parenthesized initializer ignored [-fpermissive]
  155 |   __attribute__((__externally_visible__, __alloc_size__ (1), __malloc__));
      |                                                                         ^
/usr/include/c++/14/new:156:26: error: declaration of 'operator new' as non-function
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                          ^~~~~~~~
/usr/include/c++/14/new:156:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:156:68: error: expected primary-expression before ',' token
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                    ^
/usr/include/c++/14/new:156:70: error: expected primary-expression before 'const'
  156 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                      ^~~~~
/usr/include/c++/14/new:162:26: error: declaration of 'operator new []' as non-function
  162 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                          ^~~~~~~~
/usr/include/c++/14/new:162:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  162 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/includ