Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

居然1A,本来没信心做出这道题

Posted by 15211160230 at 2017-02-26 12:56:48 on Problem 1556
#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>
#include <cmath>
#define maxn 1001
using namespace std;
struct Point{
	Point(double a,double b):x(a),y(b){}
	Point(double a,double b,int c):x(a),y(b),num(c){}
	Point(){}
	int num;
	double x,y;
};
typedef Point Vector;
struct Segment{
	Segment(Point a,Point b):Start(a),End(b){}
	Segment(){} 
	Point Start,End;	
};
struct Wall{
	Wall(double a,Segment c,Segment d):x(a),a(c),b(d){}
	Wall(){}
	double x;
	Segment a,b;	
};
Vector operator-(Point a,Point b){
	return Vector(a.x-b.x,a.y-b.y);
}
double Length(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Cross(Vector a,Vector b){	
	return a.x*b.y-a.y*b.x;
}
const double eps=1e-10;
int dcmp(double x){
	if(fabs(x)<eps)	return 0;
	else		return x>0?1:-1;
}
vector<Wall>de;
vector<Point>pot;
int N;
bool vis[maxn];
double dis[maxn];
bool JudgeSegmentInter(Segment a,Segment b)
{	double c1=Cross(a.End-a.Start,b.Start-a.Start),
    	   c2=Cross(a.End-a.Start,b.End-a.Start),
 		   c3=Cross(b.End-b.Start,a.Start-b.Start),
    	   c4=Cross(b.End-b.Start,a.End-b.Start);
	return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool JudgeRoad(Point a,Point b)
{	for(int i=0;i<de.size();++i)
	{	if(a.x<de[i].x&&de[i].x<b.x)
		{	if(!JudgeSegmentInter(Segment(a,b),de[i].a)&&
				!JudgeSegmentInter(Segment(a,b),de[i].b))
			return 0;			
		}
	}
	return 1;
}
void Spfa()
{	queue<Point>q;
	Point now;
	int i,j;
	memset(vis,0,sizeof(vis));
	for(i=0;i<pot.size();++i)	dis[i]=100000;
	q.push(pot[0]),vis[0]=1,dis[0]=0;
	while(!q.empty())
	{	now=q.front();
		q.pop();
		vis[now.num]=0;
		for(i=now.num;i<pot.size();++i)
		{	if(pot[i].x>now.x&&JudgeRoad(now,pot[i]))
			{	if(dis[pot[i].num]>dis[now.num]+Length(pot[i],now))
				{	dis[pot[i].num]=dis[now.num]+Length(pot[i],now);					
					if(!vis[pot[i].num])
					{	vis[pot[i].num]=1;
						q.push(pot[i]);			
					}				
				}	
			}
		}
	}
	printf("%.2lf\n",dis[pot.size()-1]);
}
int main()
{	int i,len;
	double a,b,c,d,e;
	while(~scanf("%d",&N)) 
	{	if(N==-1)	break;
		de.clear(),pot.clear();
		len=0;
		pot.push_back(Point(0,5,len++));
		for(i=0;i<N;++i)
		{	scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);
			pot.push_back(Point(a,b,len++));
			pot.push_back(Point(a,c,len++));
			pot.push_back(Point(a,d,len++));
			pot.push_back(Point(a,e,len++));
			de.push_back(Wall(a,Segment(Point(a,b),Point(a,c)),
								Segment(Point(a,d),Point(a,e))));
		}
		pot.push_back(Point(10,5,len++));
		Spfa();
	}
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator