Hotter Colder

Hotter Colder

时间: 1ms        内存:64M

描述:

The children's game Hotter Colder is played as follows. Player A leaves the room while player B hides an object somewhere within. Player A re-enters at position (0, 0) and then visits various other locations about the room. When player A visits a new position, player B announces ``Hotter" if this position is closer to the object than the previous position, ``Colder" if it is farther, and ``Same" if it is the same distance.

输入:

Input consists of up to 50 lines, each containing an (x, y)-coordinate pair followed by ``Hotter'', ``Colder'', or ``Same''. Each pair represents a position within the room, which may be assumed to be a square with opposite corners at (0,0) and (10,10).

输出:

For each line of input, print a line giving the total area of the region in which the object may have been placed, to two decimal places. If there is no such region, output ``0.00''.

示例输入:

10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter

示例输出:

50.00
37.50
12.50
0.00

提示:

参考答案(内存最优[2160]):

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <queue>
using namespace std;
#define INF 10000000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){
	if(fabs(x)<eps)return 0;
	return x>0?1:-1;
}
struct Point{
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;y=_y;
	}
};
Point operator + (const Point &a,const Point &b){
	return Point(a.x+b.x,a.y+b.y);
}
Point operator - (const Point &a,const Point &b){
	return Point(a.x-b.x,a.y-b.y);
}
Point operator * (const Point &a,const double &p){
	return Point(a.x*p,a.y*p);
}
Point operator / (const Point &a,const double &p){
	return Point(a.x/p,a.y/p);
}
bool operator < (const Point &a,const Point &b){
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point &b){
	return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point  a,Point b){
	return a.x*b.x+a.y*b.y;
}
double Length(Point a){
	return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){
	return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){
	return atan2(a.y,a.x);
}
double Cross(Point a,Point b){
	return a.x*b.y-a.y*b.x;
}
Point vecunit(Point a){
	return a/Length(a);
}
Point Normal(Point a){
	return Point(-a.y,a.x)/Length(a);
}
Point Rotate(Point a,double rad){
	return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
double Area2(Point a,Point b,Point c){
	return Length(Cross(b-a,c-a));
}
struct Line{
	Point p,v;
	double ang;
	Line(){};
	Line(Point p,Point v):p(p),v(v){
		ang=atan2(v.y,v.x);
	}
	bool operator < (const Line &L) const {
		return ang<L.ang;
	}
};
bool OnLeft(const Line &L,const Point &p){
	return dcmp(Cross(L.v,p-L.p))>=0;
}
Point GetLineIntersection(Point p,Point v,Point q,Point w){
	Point u=p-q;
	double t=Cross(w,u)/Cross(v,w);
	return p+v*t;
}
Point GetLineIntersection(Line a,Line b){
	return GetLineIntersection(a.p,a.v,b.p,b.v);
}
vector<Point> HPI(vector<Line> L){
	int n=L.size();
	sort(L.begin(),L.end());//将所有半平面按照极角排序。
	int first,last;
	vector<Point> p(n);
	vector<Line> q(n);
	vector<Point> ans;
	q[first=last=0]=L[0];
	for(int i=1;i<n;i++){
		while(first<last&&!OnLeft(L[i],p[last-1]))last--;//删除顶部的半平面
		while(first<last&&!OnLeft(L[i],p[first]))first++;//删除底部的半平面
		q[++last]=L[i];//将当前的半平面假如双端队列顶部。
		if(fabs(Cross(q[last].v,q[last-1].v))<eps){//对于极角相同的,选择性保留一个。
			last--;
			if(OnLeft(q[last],L[i].p))q[last]=L[i];
		}
		if(first<last)p[last-1]=GetLineIntersection(q[last-1],q[last]);//计算队列顶部半平面交点。
	}
	while(first<last&&!OnLeft(q[first],p[last-1]))last--;//删除队列顶部的无用半平面。
	if(last-first<=1)return ans;//半平面退化
	p[last]=GetLineIntersection(q[last],q[first]);//计算队列顶部与首部的交点。
	for(int i=first;i<=last;i++)ans.push_back(p[i]);//将队列中的点复制。
	return ans;
}
double PolyArea(vector<Point> p){
	int n=p.size();
	double ans=0;
	for(int i=1;i<n-1;i++)
		ans+=Cross(p[i]-p[0],p[i+1]-p[0]);
	return fabs(ans)/2;
}
Point pp[200];
int main()
{
	Point a,b;
	vector<Line> L;
    Line s;
	a=Point(0,0);b=Point(10,0);s=Line(a,b-a);L.push_back(s);
	a=Point(10,0);b=Point(10,10);s=Line(a,b-a);L.push_back(s);
	a=Point(10,10);b=Point(0,10);s=Line(a,b-a);L.push_back(s);
	a=Point(0,10);b=Point(0,0);s=Line(a,b-a);L.push_back(s);
	Point pre,cur;
	char str[100];
	int flag=0;
	while(~scanf("%lf%lf%s",&cur.x,&cur.y,str)){
		if(flag)puts("0.00");
		else{
			if(str[0]=='S'){
				flag=1;
				puts("0.00");
			}
			else{
				a=(pre+cur)/2;
				b=Normal(cur-pre);
				if(str[0]=='C')L.push_back(Line(a,b));
				if(str[0]=='H')L.push_back(Line(a,Point(-b.x,-b.y)));
				vector<Point> ans=HPI(L);
				printf("%.2f\n",PolyArea(ans));
				pre=cur;
			}
		}
	}
     return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <queue>
using namespace std;
#define INF 10000000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){
	if(fabs(x)<eps)return 0;
	return x>0?1:-1;
}
struct Point{
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;y=_y;
	}
};
Point operator + (const Point &a,const Point &b){
	return Point(a.x+b.x,a.y+b.y);
}
Point operator - (const Point &a,const Point &b){
	return Point(a.x-b.x,a.y-b.y);
}
Point operator * (const Point &a,const double &p){
	return Point(a.x*p,a.y*p);
}
Point operator / (const Point &a,const double &p){
	return Point(a.x/p,a.y/p);
}
bool operator < (const Point &a,const Point &b){
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point &b){
	return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point  a,Point b){
	return a.x*b.x+a.y*b.y;
}
double Length(Point a){
	return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){
	return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){
	return atan2(a.y,a.x);
}
double Cross(Point a,Point b){
	return a.x*b.y-a.y*b.x;
}
Point vecunit(Point a){
	return a/Length(a);
}
Point Normal(Point a){
	return Point(-a.y,a.x)/Length(a);
}
Point Rotate(Point a,double rad){
	return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
double Area2(Point a,Point b,Point c){
	return Length(Cross(b-a,c-a));
}
struct Line{
	Point p,v;
	double ang;
	Line(){};
	Line(Point p,Point v):p(p),v(v){
		ang=atan2(v.y,v.x);
	}
	bool operator < (const Line &L) const {
		return ang<L.ang;
	}
};
bool OnLeft(const Line &L,const Point &p){
	return dcmp(Cross(L.v,p-L.p))>=0;
}
Point GetLineIntersection(Point p,Point v,Point q,Point w){
	Point u=p-q;
	double t=Cross(w,u)/Cross(v,w);
	return p+v*t;
}
Point GetLineIntersection(Line a,Line b){
	return GetLineIntersection(a.p,a.v,b.p,b.v);
}
vector<Point> HPI(vector<Line> L){
	int n=L.size();
	sort(L.begin(),L.end());//将所有半平面按照极角排序。
	int first,last;
	vector<Point> p(n);
	vector<Line> q(n);
	vector<Point> ans;
	q[first=last=0]=L[0];
	for(int i=1;i<n;i++){
		while(first<last&&!OnLeft(L[i],p[last-1]))last--;//删除顶部的半平面
		while(first<last&&!OnLeft(L[i],p[first]))first++;//删除底部的半平面
		q[++last]=L[i];//将当前的半平面假如双端队列顶部。
		if(fabs(Cross(q[last].v,q[last-1].v))<eps){//对于极角相同的,选择性保留一个。
			last--;
			if(OnLeft(q[last],L[i].p))q[last]=L[i];
		}
		if(first<last)p[last-1]=GetLineIntersection(q[last-1],q[last]);//计算队列顶部半平面交点。
	}
	while(first<last&&!OnLeft(q[first],p[last-1]))last--;//删除队列顶部的无用半平面。
	if(last-first<=1)return ans;//半平面退化
	p[last]=GetLineIntersection(q[last],q[first]);//计算队列顶部与首部的交点。
	for(int i=first;i<=last;i++)ans.push_back(p[i]);//将队列中的点复制。
	return ans;
}
double PolyArea(vector<Point> p){
	int n=p.size();
	double ans=0;
	for(int i=1;i<n-1;i++)
		ans+=Cross(p[i]-p[0],p[i+1]-p[0]);
	return fabs(ans)/2;
}
Point pp[200];
int main()
{
	Point a,b;
	vector<Line> L;
    Line s;
	a=Point(0,0);b=Point(10,0);s=Line(a,b-a);L.push_back(s);
	a=Point(10,0);b=Point(10,10);s=Line(a,b-a);L.push_back(s);
	a=Point(10,10);b=Point(0,10);s=Line(a,b-a);L.push_back(s);
	a=Point(0,10);b=Point(0,0);s=Line(a,b-a);L.push_back(s);
	Point pre,cur;
	char str[100];
	int flag=0;
	while(~scanf("%lf%lf%s",&cur.x,&cur.y,str)){
		if(flag)puts("0.00");
		else{
			if(str[0]=='S'){
				flag=1;
				puts("0.00");
			}
			else{
				a=(pre+cur)/2;
				b=Normal(cur-pre);
				if(str[0]=='C')L.push_back(Line(a,b));
				if(str[0]=='H')L.push_back(Line(a,Point(-b.x,-b.y)));
				vector<Point> ans=HPI(L);
				printf("%.2f\n",PolyArea(ans));
				pre=cur;
			}
		}
	}
     return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注