Submission #3490

#	Time	Username	Problem	Language	Result	Execution time	Memory
3490		pichulia	Jogging (kriii1_J)	C++98	0 / 1	1000 ms	2872 KiB

J

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>

using namespace::std;

#define M 400000005
double PI;

struct P{
	int x, y;
}a[100005];
int n, m;
int b[100005];
int c[100005];
bool compare(P p, P q)
{
	if(p.x < q.x)
		return true;
	else if(p.x == q.x && p.y > q.y)return true;
	return false;
}
void input()
{
	PI = acos(0.0)*2;
	int i, j;
	scanf("%d %d",&n,&m);
	for(i=0; i<n; i++)
	{
		scanf("%d %d",&a[i].x,&a[i].y);
	}
	c[n-1] = a[n-1].y;
	for(i=n-2; i>=0; i--)
	{
		c[i] = a[i].y;
		if(c[i] < c[i+1])
			c[i] = c[i+1];
	}
	for(i=0; i<m; i++)
		scanf("%d",&b[i]);
	sort(a,a+n,compare);
}
struct A{
	long long int p, q;
};
bool comp(A p, A q)
{
	return (p.p * q.q < p.q * q.p);
}
void process()
{
	int i, j=0, k;
	double r,t;
	for(i=0; i<m; i++)
	{
		r=0;

		for(k=j; k<n; k++)
		{
			if(a[k].x >b[i])
				break;
		}
		j = k;
		A max, temp;
		max.p = 0; max.q = 1;
		for(; k<n; k++)
		{
			temp.p = c[k];
			temp.q = a[k].x - b[i];
			if(comp(max, temp))
			{
				temp.p = a[k].y;
				if(comp(max, temp))
					max = temp;
			}
			else
				break;
		}
		printf("%.7lf\n",atan2(max.p,max.q));
	}
}

void output()
{
}

int main()
{
	input();
	process();
	output();
	return 0;
}

• Subtask 1: 0 / 1