首页 > 代码库 > uva 10084 Hotter Colder
uva 10084 Hotter Colder
uva 10084 Hotter Colder
Problem E: Hotter Colder
The children‘s game Hotter Colder is played as follows. Player A leaves the room while player B hides an object somewhere in the room. Player A re-enters at position (0,0) and then visits various other positions 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; player B announces "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 2 decimal places. If there is no such region, output 0.00.
Sample Input
10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter
Output for Sample Input
50.00
37.50
12.50
0.00
题目大意:
有一个人玩游戏,起初是个左下角(0,0) 右上角(10,10)的矩形,有一个宝藏藏在这之间。这个人起初在(0,0) 每次走到一个点,会告诉你与原来的点相比距离宝藏近了还是远了,还是不变,根据这个每次求宝藏的范围(面积)。
解题思路:
每次相当于形成一个新的范围是凸包,只需要求这个凸包所有的点,然后按照极角排序,求面积。
这题wa了很多次,感觉代码略麻烦了一点点。
Problem E: Hotter Colder
The children‘s game Hotter Colder is played as follows. Player A leaves the room while player B hides an object somewhere in the room. Player A re-enters at position (0,0) and then visits various other positions 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; player B announces "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 2 decimal places. If there is no such region, output 0.00.
Sample Input
10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter
Output for Sample Input
50.00
37.50
12.50
0.00
题目大意:
有一个人玩游戏,起初是个左下角(0,0) 右上角(10,10)的矩形,有一个宝藏藏在这之间。这个人起初在(0,0) 每次走到一个点,会告诉你与原来的点相比距离宝藏近了还是远了,还是不变,根据这个每次求宝藏的范围(面积)。
解题思路:
每次相当于形成一个新的范围是凸包,只需要求这个凸包所有的点,然后按照极角排序,求面积。
这题wa了很多次,感觉代码略麻烦了一点点。
代码:
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <string> #include <sstream> #include <algorithm> using namespace std; const double eps=1e-6; struct point{ double x,y; point(double x0=0,double y0=0){x=x0;y=y0;} double getdis(point p){ return double(sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y))); } double xchen(point p){//this X P return x*p.y-p.x*y; } friend bool operator < (point a,point b){ if(a.y!=b.y) return a.y<b.y; else return a.x<b.x; } }; struct line{//line ax+by+c=0 double a,b,c; line(double a0=0,double b0=0,double c0=0){a=a0;b=b0;c=c0;} void setline(point p1,point p2){ a=p1.y-p2.y,b=p2.x-p1.x,c=p1.x*p2.y-p2.x*p1.y; } point getCrossPoint(line l1){//get the cross point of Line l1 and l2 point tmp; tmp.x=(l1.b*c-b*l1.c)/(l1.a*b-l1.b*a); tmp.y=(l1.c*a-c*l1.a)/(l1.a*b-l1.b*a); return tmp; } }; vector <point> p; void ini(){ p.clear(); p.push_back(point(0,0)); p.push_back(point(10,0)); p.push_back(point(10,10)); p.push_back(point(0,10)); } line getLine(point p1,point p2){//get the Line that cross point p1 + p2/2 line tmpLine; tmpLine.a=p2.x-p1.x; tmpLine.b=p2.y-p1.y; tmpLine.c=(p1.x*p1.x-p2.x*p2.x+p1.y*p1.y-p2.y*p2.y)/2.0; return tmpLine; } double xchen(point a,point b,point c){ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } bool cmp(point a,point b){ if(fabs(xchen(p[0],a,b))<eps) return a.getdis(p[0])<b.getdis(p[0]); else return xchen(p[0],a,b)>0; } void deal(point s,point d,int flag){ line l2=getLine(s,d); vector <point> v; for(int i=0;i<p.size();i++){ if(flag<0){ if(p[i].getdis(s)<p[i].getdis(d)){ v.push_back(p[i]); } }else{ if(p[i].getdis(s)>p[i].getdis(d)){ v.push_back(p[i]); } } } p.push_back(p[0]); for(int i=1;i<p.size();i++){ line l1; l1.setline(p[i-1],p[i]); if( fabs(l1.a*l2.b-l1.b*l2.a)<eps ) continue; point tmp=l2.getCrossPoint(l1); if( fabs( fabs(tmp.x-p[i-1].x)+fabs(tmp.x-p[i].x)-fabs(p[i].x-p[i-1].x) ) > eps ) continue; if( fabs( fabs(tmp.y-p[i-1].y)+fabs(tmp.y-p[i].y)-fabs(p[i].y-p[i-1].y) ) > eps ) continue; v.push_back(tmp); } p.clear(); sort(v.begin(),v.end()); for(int i=0;i<v.size();i++){ if(p.size()>0 && ( fabs(p.back().x-v[i].x)<eps && fabs(p.back().y-v[i].y)<eps ) ) continue; p.push_back(v[i]); } if(p.size()>=1) sort(++p.begin(),p.end(),cmp); } double getarea(){ double sum=0; for(int i=1;i<p.size()-1;i++){ point p1=point(p[i].x-p[0].x,p[i].y-p[0].y); point p2=point(p[i+1].x-p[0].x,p[i+1].y-p[0].y); sum+=fabs(p2.xchen(p1))/2.0; } return sum; } void solve(){ string str; point s(0,0),d; double area=getarea(); while(cin>>d.x>>d.y>>str){ //if(d.x<-eps || d.y<-eps || d.x>10+eps || d.y>10+eps){ //printf("0.00\n"); //break; //} if(str=="Colder"){ if(fabs(d.x-s.x)>eps || fabs(d.y-s.y)>eps){ deal(s,d,-1); area=getarea(); } } else if(str=="Hotter"){ if(fabs(d.x-s.x)>eps || fabs(d.y-s.y)>eps){ deal(s,d,1); area=getarea(); } } else{ area=0; } printf("%.2lf\n",area); if(area<eps) break; s=d; } while(cin>>d.x>>d.y>>str){ printf("0.00\n"); continue; } } int main(){ ini(); solve(); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。