답안 #27279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27279 2017-07-12T07:02:02 Z 구사과(#1145) Dragon 2 (JOI17_dragon2) C++
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

struct pnt{
	int x, y, c;
	int r1, r2;
}a[30005], s, e;

lint ccw(pnt a, pnt b, pnt c){
	return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (c.x - a.x) * (b.y - a.y);
}

int n, m;
int stx[30005], sty[30005], edx[30005], edy[30005];

void label1(){
	sort(a, a+n, [&](const pnt &p, const pnt &q){
		bool bh1 = ccw(s, e, p) > 0;
		bool bh2 = ccw(s, e, q) > 0;
		if(bh1 != bh2) return bh1 > bh2;
		return ccw(s, p, q) > 0;
	});
	int dv = 0;
	for(int i=0; i<n; i++){
		a[i].r1 = i;
		if(ccw(s, e, a[i]) > 0) dv = i+1;
	}
	int p = 0;
	for(int i=dv; i<n; i++){
		while(p < dv && ccw(s, a[i], a[p]) > 0) p++;
		stx[i] = i;
		edx[i] = p;
	}
	p = dv;
	for(int i=0; i<dv; i++){
		while(p < n && ccw(s, a[i], a[p]) > 0) p++;
		stx[i] = p;
		edx[i] = i;
	}
}

void label2(){
	sort(a, a+n, [&](const pnt &p, const pnt &q){
		bool bh1 = ccw(s, e, p) > 0;
		bool bh2 = ccw(s, e, q) > 0;
		if(bh1 != bh2) return bh1 > bh2;
		return ccw(e, p, q) > 0;
	});
	int dv = 0;
	for(int i=0; i<n; i++){
		a[i].r2 = i;
		if(ccw(s, e, a[i]) > 0) dv = i+1;
	}
	int p = 0;
	for(int i=dv; i<n; i++){
		while(p < dv && ccw(e, a[i], a[p]) > 0) p++;
		sty[i] = p;
		edy[i] = i;
	}
	p = dv;
	for(int i=0; i<dv; i++){
		while(p < n && ccw(e, a[i], a[p]) > 0) p++;
		sty[i] = i;
		edy[i] = p;
	}
}

vector<pi> grp[30005];
map<pi, int> mp;
int refer[30005], ans[30005];

void add_sweep(int sx, int ex, int sy, int ey, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(sx <= i.first && i.first <= ex && sy <= i.second && i.second <= ey) ans[idx]++;
	}
}

void add_sweep2(int y, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
	}
}

void add_sweep3(int x, int y, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
	}
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
	}
	scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
	label1();
	label2();
	for(int i=0; i<n; i++){
		grp[a[i].c].push_back(pi(a[i].r1, a[i].r2));
	}
	int q;
	scanf("%d",&q);
	for(int i=1; i<=q; i++){
		int x, y;
		scanf("%d %d",&x,&y);
		if(mp.find(pi(x, y)) != mp.end()){
			refer[i] = mp[pi(x, y)];
			continue;
		}
		int ret = 0, qi = i;
		if(grp[x].size() < grp[y].size()){
			for(auto &i : grp[x]){
				add_sweep(0, edx[i.first] - 1, sty[i.second], edy[i.second] - 1, y, qi);
				add_sweep(stx[i.first], n-1, sty[i.second], edy[i.second] - 1, y, qi);
			}
		}
		else{
			for(auto &j : grp[y]){
				add_sweep2(j.second, x, i);
				add_sweep3(j.first, j.second, x, i);
			}
		}
		/*
		for(auto &i : grp[x]){
			for(auto &j : grp[y]){
				bool xma = !(edx[i.first] <= j.first && j.first < stx[i.first]);
				bool yma = (sty[i.second] <= j.second && j.second < edy[i.second]);
				if(xma && yma) ret++;
			}
		}*/
		mp[pi(x, y)] = i;
	}
	for(int i=1; i<=q; i++){
		if(refer[i]) printf("%d\n", ans[refer[i]]);
		else printf("%d\n", ans[i]);
	}
}

Compilation message

dragon2.cpp: In function 'void label1()':
dragon2.cpp:25:2: warning: lambda expressions only available with -std=c++11 or -std=gnu++11
  });
  ^
dragon2.cpp:25:3: error: no matching function for call to 'sort(pnt [30005], pnt*, label1()::<lambda(const pnt&, const pnt&)>)'
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4689:5: note: candidate: template<class _RAIter> void std::sort(_RAIter, _RAIter)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     ^
/usr/include/c++/5/bits/stl_algo.h:4689:5: note:   template argument deduction/substitution failed:
dragon2.cpp:25:3: note:   candidate expects 2 arguments, 3 provided
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4718:5: note: candidate: template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
/usr/include/c++/5/bits/stl_algo.h:4718:5: note:   template argument deduction/substitution failed:
dragon2.cpp: In substitution of 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = pnt*; _Compare = label1()::<lambda(const pnt&, const pnt&)>]':
dragon2.cpp:25:3:   required from here
dragon2.cpp:25:3: error: template argument for 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)' uses local type 'label1()::<lambda(const pnt&, const pnt&)>'
  });
   ^
dragon2.cpp:25:3: error:   trying to instantiate 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
dragon2.cpp: In function 'void label2()':
dragon2.cpp:51:2: warning: lambda expressions only available with -std=c++11 or -std=gnu++11
  });
  ^
dragon2.cpp:51:3: error: no matching function for call to 'sort(pnt [30005], pnt*, label2()::<lambda(const pnt&, const pnt&)>)'
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4689:5: note: candidate: template<class _RAIter> void std::sort(_RAIter, _RAIter)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     ^
/usr/include/c++/5/bits/stl_algo.h:4689:5: note:   template argument deduction/substitution failed:
dragon2.cpp:51:3: note:   candidate expects 2 arguments, 3 provided
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4718:5: note: candidate: template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
/usr/include/c++/5/bits/stl_algo.h:4718:5: note:   template argument deduction/substitution failed:
dragon2.cpp: In substitution of 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = pnt*; _Compare = label2()::<lambda(const pnt&, const pnt&)>]':
dragon2.cpp:51:3:   required from here
dragon2.cpp:51:3: error: template argument for 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)' uses local type 'label2()::<lambda(const pnt&, const pnt&)>'
  });
   ^
dragon2.cpp:51:3: error:   trying to instantiate 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
dragon2.cpp: In function 'void add_sweep(int, int, int, int, int, int)':
dragon2.cpp:76:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : grp[gnum]){
      ^
dragon2.cpp:76:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : grp[gnum]){
            ^
dragon2.cpp:76:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : grp[gnum]){
                ^
dragon2.cpp:77:14: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(sx <= i.first && i.first <= ex && sy <= i.second && i.second <= ey) ans[idx]++;
              ^
dragon2.cpp:77:25: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(sx <= i.first && i.first <= ex && sy <= i.second && i.second <= ey) ans[idx]++;
                         ^
dragon2.cpp:77:48: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(sx <= i.first && i.first <= ex && sy <= i.second && i.second <= ey) ans[idx]++;
                                                ^
dragon2.cpp:77:60: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(sx <= i.first && i.first <= ex && sy <= i.second && i.second <= ey) ans[idx]++;
                                                            ^
dragon2.cpp: In function 'void add_sweep2(int, int, int)':
dragon2.cpp:82:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : grp[gnum]){
      ^
dragon2.cpp:82:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : grp[gnum]){
            ^
dragon2.cpp:82:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : grp[gnum]){
                ^
dragon2.cpp:83:12: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
            ^
dragon2.cpp:83:38: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
                                      ^
dragon2.cpp: In function 'void add_sweep3(int, int, int, int)':
dragon2.cpp:88:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : grp[gnum]){
      ^
dragon2.cpp:88:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : grp[gnum]){
            ^
dragon2.cpp:88:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : grp[gnum]){
                ^
dragon2.cpp:89:12: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
            ^
dragon2.cpp:89:37: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
                                     ^
dragon2.cpp:89:53: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
                                                     ^
dragon2.cpp:89:79: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
                                                                               ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:115:8: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
    for(auto &i : grp[x]){
        ^
dragon2.cpp:115:14: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
    for(auto &i : grp[x]){
              ^
dragon2.cpp:115:18: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
    for(auto &i : grp[x]){
                  ^
dragon2.cpp:116:24: error: request for member 'first' in 'i', which is of non-class type 'int'
     add_sweep(0, edx[i.first] - 1, sty[i.second], edy[i.second] - 1, y, qi);
                        ^
dragon2.cpp:116:42: error: request for member 'second' in 'i', which is of non-class type 'int'
     add_sweep(0, edx[i.first] - 1, sty[i.second], edy[i.second] - 1, y, qi);
                                          ^
dragon2.cpp:116:57: error: request for member 'second' in 'i', which is of non-class type 'int'
     add_sweep(0, edx[i.first] - 1, sty[i.second], edy[i.second] - 1, y, qi);
                                                         ^
dragon2.cpp:117:21: error: request for member 'first' in 'i', which is of non-class type 'int'
     add_sweep(stx[i.first], n-1, sty[i.second], edy[i.second] - 1, y, qi);
                     ^
dragon2.cpp:117:40: error: request for member 'second' in 'i', which is of non-class type 'int'
     add_sweep(stx[i.first], n-1, sty[i.second], edy[i.second] - 1, y, qi);
                                        ^
dragon2.cpp:117:55: error: request for member 'second' in 'i', which is of non-class type 'int'
     add_sweep(stx[i.first], n-1, sty[i.second], edy[i.second] - 1, y, qi);
                                                       ^
dragon2.cpp:121:8: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
    for(auto &j : grp[y]){
        ^
dragon2.cpp:121:14: error: ISO C++ forbids declaration of 'j' with no type [-fpermissive]
    for(auto &j : grp[y]){
              ^
dragon2.cpp:121:18: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
    for(auto &j : grp[y]){
                  ^
dragon2.cpp:122:18: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep2(j.second, x, i);
                  ^
dragon2.cpp:123:18: error: request for member 'first' in 'j', which is of non-class type 'int'
     add_sweep3(j.first, j.second, x, i);
                  ^
dragon2.cpp:123:27: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep3(j.first, j.second, x, i);
                           ^
dragon2.cpp:113:7: warning: unused variable 'ret' [-Wunused-variable]
   int ret = 0, qi = i;
       ^
dragon2.cpp:94:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
dragon2.cpp:96:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
                                            ^
dragon2.cpp:98:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
                                          ^
dragon2.cpp:105:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
dragon2.cpp:108:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^