Submission #4269

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4269	2013-09-08T09:50:30 Z	joonas	Jogging (kriii1_J)	C++	0 / 1	1000 ms	3392 KB

J

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

vector<int> xs;
vector<double> res;
vector< pair<int,int> > ns;
int lastid;

bool descend(int i,int j){ return (i<j); }

void f( int x ){
	//printf("%d ----\n", x );
	int _dx = ns[lastid].first - x, _dy = ns[lastid].second;
	double _ds = sqrt((double)(_dx*_dx)+(_dy*_dy));
	double ret = asin(_dy/_ds);

	int i = lastid;
	for(; i >= 0; --i){
		if( ns[i].first <= x ) break;	//x1~
		int dx = ns[i].first - x, dy = ns[i].second;
		double ds = sqrt((double)(dx*dx)+(dy*dy));
		if( asin(dy/ds) > asin(_dy/_ds) ){
			ret = asin(dy/ds);
			lastid = i;
		}
		//printf("(%d,%d):%.7f\n", ns[i].first, dy, asin(dy/ds));
	}
	//printf("[(%d,%d):%.7f]\n", ns[lastid].first, ns[lastid].second, ret);
	res.push_back(ret);
}

int main(){
	int i, n, m, x, y;
	scanf("%d %d", &n, &m);
	for(i=0; i < n; ++i){
		scanf("%d %d", &x, &y);
		ns.push_back( pair<int,int>(x,y) );
	}
	lastid = ns.size()-1;

	for(i=0; i < m; ++i){
		scanf("%d", &x);
		xs.push_back( x );
	}

	for(i=xs.size()-1; i >= 0; --i) f(xs[i]);
	for(i=res.size()-1; i >= 0; --i) printf("%.7f\n", res[i]);

	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	3392 KB	Program timed out
2	Halted	0 ms	0 KB	-