답안 #152469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152469	2019-09-08T04:59:40 Z	Mahotsukai	최적의 팀 구성 (FXCUP4_squad)	C++17	컴파일 오류	0 ms	0 KB

squad

struct point{
	ll x, y;
	point(pll p): x(p.first), y(p.second){}
	point(ll x = 0, ll y = 0): x(x), y(y){}
	bool operator<(const point &other) const{
		return x < other.x || (x == other.x && y < other.y);
	}
	point operator+(const point &other) const{
		return point(x + other.x, y + other.y);
	}
	point operator+=(const point &other){
		return *this = *this + other;
	}
	point operator-(const point &other) const{
		return point(x - other.x, y - other.y);
	}
	point operator-=(const point &other){
		return *this = *this - other;
	}
	bool operator==(const point &other) const{
		return x == other.x && y == other.y;
	}
	ll operator*(const point &other) const{
		return x * other.x + y * other.y;
	}
};
istream &operator>>(istream &in, point &p){
	cin >> p.x >> p.y;
	return in;
}
ostream &operator<<(ostream &out, const point &p){
	cout << "(" << p.x << ", " << p.y << ")";
	return out;
}
ll ori(const point &p, const point &q, const point &r){
	return p.x * q.y + q.x * r.y + r.x * p.y - p.y * q.x - q.y * r.x - r.y * p.x;
}
struct convhull{
	int N, R;
	vector<point> ch;
	convhull(vector<point> arr = vector<point>(), bool sorted = false){
		if(!sorted){
			sort(all(arr));
		}
		arr.resize(unique(all(arr)) - arr.begin());
		if(arr.size() <= 1){
			ch = arr;
			N = R = arr.size();
			if(N) R --;
			return;
		}
		vector<point> upper;
		point p = arr.front(), q = arr.back();
		upper.push_back(p);
		for(int i = 1; i < arr.size(); i ++){
			if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
				while(upper.size() >= 2 && ori(upper[upper.size() - 2], upper[upper.size() - 1], arr[i]) >= 0){
					upper.pop_back();
				}
				upper.push_back(arr[i]);
			}
		}
		ch.push_back(p), ch.push_back(q);
		for(int i = upper.size() - 2; i; i --) ch.push_back(upper[i]);
		N = ch.size();
		R = 1;
	}
	vector<point> linearize() const{
		if(N <= 1) return ch;
		int i = 0, j = N - 1;
		vector<point> res(N);
		int cnt = 0;
		while(i <= j){
			if(ch[i] < ch[j]) res[cnt ++] = ch[i ++];
			else res[cnt ++] = ch[j --];
		}
		return res;
	}
	int max_element(ll x, ll y){
		point p(x, y);
		int l = R, r = N;
		while(r - l > 3){
			int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
			p * ch[m1] <= p * ch[m2] ? l = m1 : r = m2;
		}
		int res = 0;
		for(int i = l; i < r; i ++) if(p * ch[res] < p * ch[i]) res = i;
		return res;
	}
	convhull operator+(const convhull &other) const{
		if(!N || !other.N) return convhull();
		vector<point> temp1(ch), temp2(other.ch);
		for(int i = 0; i + 1 < N; i ++) temp1[i] = ch[i + 1] - ch[i];
		for(int i = 0; i + 1 < other.N; i ++) temp2[i] = other.ch[i + 1] - other.ch[i];
		temp1.back() = ch.front() - ch.back();
		temp2.back() = other.ch.front() - other.ch.back();
		function<bool(point, point)> cmp = [&](point p, point q){
			int typep = 1, typeq = 1;
			if(p.x > 0 || !p.x && p.y >= 0) typep = 0;
			if(q.x > 0 || !q.x && q.y >= 0) typeq = 0;
			if(typep != typeq) return typep < typeq;
			return ori(p, q, point(0, 0)) > 0;
		};
		vector<point> temp(N + other.N);
		int cnt = 0;
		int i = 0, j = 0;
		while(i < N && j < other.N){
			if(cmp(temp1[i], temp2[j])) temp[cnt ++] = temp1[i ++];
			else temp[cnt ++] = temp2[j ++];
		}
		for(; i < N; i ++) temp[cnt ++] = temp1[i ++];
		for(; j < other.N; j ++) temp[cnt ++] = temp2[j ++];
		convhull res;
		res.N = N + other.N;
		res.ch.resize(res.N);
		cnt = 0;
		res.ch[cnt ++] = ch[0] + other.ch[0];
		for(int i = 0; i + 1 < res.N; i ++){
			res.ch[cnt ++] = res.ch[cnt - 1] + temp[i];
		}
		res.R = std::max_element(all(res.ch)) - res.ch.begin();
		return res;
	}
	convhull operator^(const convhull &other) const{
		if(!N) return other;
		if(!other.N) return *this;
		auto temp1 = linearize(), temp2 = other.linearize();
		vector<point> res(temp1.size() + temp2.size());
		merge(all(temp1), all(temp2), res.begin());
		return convhull(res, true);
	}
	convhull operator-() const{
		convhull res(*this);
		res.R = N - R;
		if(N == 1) res.R = 0;
		for(int i = 0; i + R < N; i ++) res.ch[i] = point(-ch[i + R].x, -ch[i + R].y);
		for(int i = N - R; i < N; i ++) res.ch[i] = point(-ch[i + R - N].x, -ch[i + R - N].y);
		return res;
	}
};

Compilation message

squad.cpp:2:2: error: 'll' does not name a type
  ll x, y;
  ^~
squad.cpp:3:12: error: expected ')' before 'p'
  point(pll p): x(p.first), y(p.second){}
            ^
squad.cpp:4:11: error: expected ')' before 'x'
  point(ll x = 0, ll y = 0): x(x), y(y){}
           ^
squad.cpp:23:2: error: 'll' does not name a type
  ll operator*(const point &other) const{
  ^~
squad.cpp: In member function 'bool point::operator<(const point&) const':
squad.cpp:6:10: error: 'x' was not declared in this scope
   return x < other.x || (x == other.x && y < other.y);
          ^
squad.cpp:6:20: error: 'const struct point' has no member named 'x'
   return x < other.x || (x == other.x && y < other.y);
                    ^
squad.cpp:6:37: error: 'const struct point' has no member named 'x'
   return x < other.x || (x == other.x && y < other.y);
                                     ^
squad.cpp:6:42: error: 'y' was not declared in this scope
   return x < other.x || (x == other.x && y < other.y);
                                          ^
squad.cpp:6:52: error: 'const struct point' has no member named 'y'
   return x < other.x || (x == other.x && y < other.y);
                                                    ^
squad.cpp: In member function 'point point::operator+(const point&) const':
squad.cpp:9:16: error: 'x' was not declared in this scope
   return point(x + other.x, y + other.y);
                ^
squad.cpp:9:26: error: 'const struct point' has no member named 'x'
   return point(x + other.x, y + other.y);
                          ^
squad.cpp:9:29: error: 'y' was not declared in this scope
   return point(x + other.x, y + other.y);
                             ^
squad.cpp:9:39: error: 'const struct point' has no member named 'y'
   return point(x + other.x, y + other.y);
                                       ^
squad.cpp: In member function 'point point::operator-(const point&) const':
squad.cpp:15:16: error: 'x' was not declared in this scope
   return point(x - other.x, y - other.y);
                ^
squad.cpp:15:26: error: 'const struct point' has no member named 'x'
   return point(x - other.x, y - other.y);
                          ^
squad.cpp:15:29: error: 'y' was not declared in this scope
   return point(x - other.x, y - other.y);
                             ^
squad.cpp:15:39: error: 'const struct point' has no member named 'y'
   return point(x - other.x, y - other.y);
                                       ^
squad.cpp: In member function 'bool point::operator==(const point&) const':
squad.cpp:21:10: error: 'x' was not declared in this scope
   return x == other.x && y == other.y;
          ^
squad.cpp:21:21: error: 'const struct point' has no member named 'x'
   return x == other.x && y == other.y;
                     ^
squad.cpp:21:26: error: 'y' was not declared in this scope
   return x == other.x && y == other.y;
                          ^
squad.cpp:21:37: error: 'const struct point' has no member named 'y'
   return x == other.x && y == other.y;
                                     ^
squad.cpp: At global scope:
squad.cpp:27:1: error: 'istream' does not name a type
 istream &operator>>(istream &in, point &p){
 ^~~~~~~
squad.cpp:31:1: error: 'ostream' does not name a type
 ostream &operator<<(ostream &out, const point &p){
 ^~~~~~~
squad.cpp:35:1: error: 'll' does not name a type
 ll ori(const point &p, const point &q, const point &r){
 ^~
squad.cpp:40:2: error: 'vector' does not name a type
  vector<point> ch;
  ^~~~~~
squad.cpp:41:17: error: expected ')' before '<' token
  convhull(vector<point> arr = vector<point>(), bool sorted = false){
                 ^
squad.cpp:68:2: error: 'vector' does not name a type
  vector<point> linearize() const{
  ^~~~~~
squad.cpp:79:18: error: 'll' has not been declared
  int max_element(ll x, ll y){
                  ^~
squad.cpp:79:24: error: 'll' has not been declared
  int max_element(ll x, ll y){
                        ^~
squad.cpp: In member function 'int convhull::max_element(int, int)':
squad.cpp:80:15: error: no matching function for call to 'point::point(int&, int&)'
   point p(x, y);
               ^
squad.cpp:1:8: note: candidate: constexpr point::point()
 struct point{
        ^~~~~
squad.cpp:1:8: note:   candidate expects 0 arguments, 2 provided
squad.cpp:1:8: note: candidate: constexpr point::point(const point&)
squad.cpp:1:8: note:   candidate expects 1 argument, 2 provided
squad.cpp:1:8: note: candidate: constexpr point::point(point&&)
squad.cpp:1:8: note:   candidate expects 1 argument, 2 provided
squad.cpp:84:8: error: 'ch' was not declared in this scope
    p * ch[m1] <= p * ch[m2] ? l = m1 : r = m2;
        ^~
squad.cpp:87:38: error: 'ch' was not declared in this scope
   for(int i = l; i < r; i ++) if(p * ch[res] < p * ch[i]) res = i;
                                      ^~
squad.cpp: In member function 'convhull convhull::operator+(const convhull&) const':
squad.cpp:92:3: error: 'vector' was not declared in this scope
   vector<point> temp1(ch), temp2(other.ch);
   ^~~~~~
squad.cpp:92:15: error: expected primary-expression before '>' token
   vector<point> temp1(ch), temp2(other.ch);
               ^
squad.cpp:92:23: error: 'ch' was not declared in this scope
   vector<point> temp1(ch), temp2(other.ch);
                       ^~
squad.cpp:92:23: note: suggested alternative: 'char'
   vector<point> temp1(ch), temp2(other.ch);
                       ^~
                       char
squad.cpp:92:17: error: 'temp1' was not declared in this scope
   vector<point> temp1(ch), temp2(other.ch);
                 ^~~~~
squad.cpp:92:40: error: 'const struct convhull' has no member named 'ch'
   vector<point> temp1(ch), temp2(other.ch);
                                        ^~
squad.cpp:92:28: error: 'temp2' was not declared in this scope
   vector<point> temp1(ch), temp2(other.ch);
                            ^~~~~
squad.cpp:94:58: error: 'const struct convhull' has no member named 'ch'
   for(int i = 0; i + 1 < other.N; i ++) temp2[i] = other.ch[i + 1] - other.ch[i];
                                                          ^~
squad.cpp:94:76: error: 'const struct convhull' has no member named 'ch'
   for(int i = 0; i + 1 < other.N; i ++) temp2[i] = other.ch[i + 1] - other.ch[i];
                                                                            ^~
squad.cpp:96:24: error: 'const struct convhull' has no member named 'ch'
   temp2.back() = other.ch.front() - other.ch.back();
                        ^~
squad.cpp:96:43: error: 'const struct convhull' has no member named 'ch'
   temp2.back() = other.ch.front() - other.ch.back();
                                           ^~
squad.cpp:97:3: error: 'function' was not declared in this scope
   function<bool(point, point)> cmp = [&](point p, point q){
   ^~~~~~~~
squad.cpp:97:3: note: suggested alternative: 'union'
   function<bool(point, point)> cmp = [&](point p, point q){
   ^~~~~~~~
   union
squad.cpp:97:29: error: expression list treated as compound expression in functional cast [-fpermissive]
   function<bool(point, point)> cmp = [&](point p, point q){
                             ^
squad.cpp:97:12: error: expected primary-expression before 'bool'
   function<bool(point, point)> cmp = [&](point p, point q){
            ^~~~
squad.cpp:104:15: error: expected primary-expression before '>' token
   vector<point> temp(N + other.N);
               ^
squad.cpp:104:17: error: 'temp' was not declared in this scope
   vector<point> temp(N + other.N);
                 ^~~~
squad.cpp:108:7: error: 'cmp' was not declared in this scope
    if(cmp(temp1[i], temp2[j])) temp[cnt ++] = temp1[i ++];
       ^~~
squad.cpp:115:7: error: 'struct convhull' has no member named 'ch'
   res.ch.resize(res.N);
       ^~
squad.cpp:117:7: error: 'struct convhull' has no member named 'ch'
   res.ch[cnt ++] = ch[0] + other.ch[0];
       ^~
squad.cpp:117:34: error: 'const struct convhull' has no member named 'ch'
   res.ch[cnt ++] = ch[0] + other.ch[0];
                                  ^~
squad.cpp:119:8: error: 'struct convhull' has no member named 'ch'
    res.ch[cnt ++] = res.ch[cnt - 1] + temp[i];
        ^~
squad.cpp:119:25: error: 'struct convhull' has no member named 'ch'
    res.ch[cnt ++] = res.ch[cnt - 1] + temp[i];
                         ^~
squad.cpp:121:16: error: 'max_element' is not a member of 'std'
   res.R = std::max_element(all(res.ch)) - res.ch.begin();
                ^~~~~~~~~~~
squad.cpp:121:36: error: 'struct convhull' has no member named 'ch'
   res.R = std::max_element(all(res.ch)) - res.ch.begin();
                                    ^~
squad.cpp:121:28: error: 'all' was not declared in this scope
   res.R = std::max_element(all(res.ch)) - res.ch.begin();
                            ^~~
squad.cpp:121:47: error: 'struct convhull' has no member named 'ch'
   res.R = std::max_element(all(res.ch)) - res.ch.begin();
                                               ^~
squad.cpp: In member function 'convhull convhull::operator^(const convhull&) const':
squad.cpp:127:16: error: 'linearize' was not declared in this scope
   auto temp1 = linearize(), temp2 = other.linearize();
                ^~~~~~~~~
squad.cpp:128:3: error: 'vector' was not declared in this scope
   vector<point> res(temp1.size() + temp2.size());
   ^~~~~~
squad.cpp:128:15: error: expected primary-expression before '>' token
   vector<point> res(temp1.size() + temp2.size());
               ^
squad.cpp:128:36: error: 'temp2' was not declared in this scope
   vector<point> res(temp1.size() + temp2.size());
                                    ^~~~~
squad.cpp:128:17: error: 'res' was not declared in this scope
   vector<point> res(temp1.size() + temp2.size());
                 ^~~
squad.cpp:129:9: error: 'all' was not declared in this scope
   merge(all(temp1), all(temp2), res.begin());
         ^~~
squad.cpp:129:3: error: 'merge' was not declared in this scope
   merge(all(temp1), all(temp2), res.begin());
   ^~~~~
squad.cpp: In member function 'convhull convhull::operator-() const':
squad.cpp:136:39: error: 'struct convhull' has no member named 'ch'
   for(int i = 0; i + R < N; i ++) res.ch[i] = point(-ch[i + R].x, -ch[i + R].y);
                                       ^~
squad.cpp:136:54: error: 'ch' was not declared in this scope
   for(int i = 0; i + R < N; i ++) res.ch[i] = point(-ch[i + R].x, -ch[i + R].y);
                                                      ^~
squad.cpp:137:39: error: 'struct convhull' has no member named 'ch'
   for(int i = N - R; i < N; i ++) res.ch[i] = point(-ch[i + R - N].x, -ch[i + R - N].y);
                                       ^~
squad.cpp:137:54: error: 'ch' was not declared in this scope
   for(int i = N - R; i < N; i ++) res.ch[i] = point(-ch[i + R - N].x, -ch[i + R - N].y);
                                                      ^~