Submission #4238

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4238	2013-09-06T06:12:05 Z	sjw0687	Jogging (kriii1_J)	C++	Compilation error	0 ms	0 KB

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;

	const bool operator < (const 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

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:2215:4: error: passing 'const Star' as 'this' argument of 'const bool Star::operator<(Star)' discards qualifiers [-fpermissive]