Submission #4235

#	Time	Username	Problem	Language	Result	Execution time	Memory
4235		sjw0687	Jogging (kriii1_J)	C++98	Compilation error	0 ms	0 KiB

J

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;

const int INF = INT_MAX / 2;
typedef pair<int, int> pii;

struct Star {
	int x,y;

	bool operator < (Star& rhs) {
		return x != rhs.x ? x < rhs.x : y > rhs.y;
	}
};

int n;
int m;
Star stars[10001];
int xRest[10000];
double answer[10000];

int minX[10000];
stack< pii > s;

int calXBoundary(Star& s1, Star& s2)
{
	double a = (s2.y - s1.y) / (s2.x - s1.x);
	double b = s1.y - a * s1.x;

	return -b/a;
}

int main(void)
{
	cin >> n >> m;
	for(int i=0; i<n; i++) {
		cin >> stars[i].x >> stars[i].y;
	}
	stars[n].x = 100000001; stars[n].y = 0;
	for(int i=0; i<m; i++)
		cin >> xRest[i];
	sort(stars, stars+n);

	int iStar = n;
	s.push( pii(n, -INF) );
	for(int i=m-1; i>=0; i--) {
		int& x = xRest[i];

		while(x <= s.top().second) {
			s.pop();
		}

		while(iStar > 0 && x < stars[iStar-1].x) {
			Star& newStar = stars[iStar-1];
			while(!s.empty() && newStar.y >= stars[s.top().first].y) {
				s.pop();
			}

			if( !s.empty() )
				s.push( pii(iStar-1, calXBoundary(newStar, stars[s.top().first])) );
			else
				s.push( pii(iStar-1, -INF) );
			while(x <= s.top().second) {
				s.pop();
			}

			iStar--;
		}

		answer[i] = atan( (double) stars[s.top().first].y / (stars[s.top().first].x - x) );
	}

	for(int i=0; i<m; i++) {
		cout.precision(7); cout.setf(ios::fixed);
		cout << answer[i] << endl;
	}
	
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/4.6/algorithm:63:0,
                 from J.cpp:7:
/usr/include/c++/4.6/bits/stl_algo.h: In function '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = Star*, _Tp = Star]':
/usr/include/c++/4.6/bits/stl_algo.h:2253:70:   instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = Star*]'
/usr/include/c++/4.6/bits/stl_algo.h:2284:54:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = Star*, _Size = long int]'
/usr/include/c++/4.6/bits/stl_algo.h:5407:4:   instantiated from 'void std::sort(_RAIter, _RAIter) [with _RAIter = Star*]'
J.cpp:57:21:   instantiated from here
/usr/include/c++/4.6/bits/stl_algo.h:2212:4: error: no match for 'operator<' in '* __first < __pivot'
/usr/include/c++/4.6/bits/stl_algo.h:2212:4: note: candidates are:
J.cpp:26:7: note: bool Star::operator<(Star&)
J.cpp:26:7: note:   no known conversion for argument 1 from 'const Star' to 'Star&'
/usr/include/c++/4.6/bits/stl_pair.h:207:5: note: template<class _T1, class _T2> bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
/usr/include/c++/4.6/bits/stl_iterator.h:291:5: note: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_iterator.h:341:5: note: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
/usr/include/c++/4.6/bits/basic_string.h:2510:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.h:2522:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
/usr/include/c++/4.6/bits/basic_string.h:2534:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/stl_vector.h:1290:5: note: template<class _Tp, class _Alloc> bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)
/usr/include/c++/4.6/bits/stl_list.h:1593:5: note: template<class _Tp, class _Alloc> bool std::operator<(const std::list<_Tp, _Alloc>&, const std::list<_Tp, _Alloc>&)
/usr/include/c++/4.6/bits/stl_tree.h:866:5: note: template<class _Key, class _Val, class _KeyOfValue, class _Compare, class _Alloc> bool std::operator<(const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&, const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_map.h:899:5: note: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::map<_Key, _Tp, _Compare, _Alloc>&, const std::map<_Key, _Tp, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_multimap.h:817:5: note: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::multimap<_Key, _Tp, _Compare, _Alloc>&, const std::multimap<_Key, _Tp, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_set.h:713:5: note: template<class _Key, class _Compare, class _Alloc> bool std::operator<(const std::set<_Key, _Compare, _Alloc>&, const std::set<_Key, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_multiset.h:696:5: note: template<class _Key, class _Compare, class _Alloc> bool std::operator<(const std::multiset<_Key, _Compare, _Alloc>&, const std::multiset<_Key, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_deque.h:272:5: note: template<class _Tp, class _Ref, class _Ptr> bool std::operator<(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _Ref, _Ptr>&)
/usr/include/c++/4.6/bits/stl_deque.h:280:5: note: template<class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> bool std::operator<(const std::_Deque_iterator<_Tp, _RefL, _PtrL>&, const std::_Deque_iterator<_Tp, _RefR, _PtrR>&)
/usr/include/c++/4.6/bits/stl_deque.h:1935:5: note: template<class _Tp, class _Alloc> bool std::operator<(const std::deque<_Tp, _Alloc>&, const std::deque<_Tp, _Alloc>&)
/usr/include/c++/4.6/bits/stl_queue.h:284:5: note: template<class _Tp, class _Seq> bool std::operator<(const std::queue<_Tp, _Seq>&, const std::queue<_Tp, _Seq>&)
/usr/include/c++/4.6/bits/stl_stack.h:259:5: note: template<class _Tp, class _Seq> bool std::operator<(const std::stack<_Tp, _Seq>&, const std::stack<_Tp, _Seq>&)
/usr/include/c++/4.6/bits/stl_algo.h:2215:4: error: passing 'const Star' as 'this' argument of 'bool Star::operator<(Star&)' discards qualifiers [-fpermissive]