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

真是惨。。。(附代妈)

Posted by KatrineYang at 2016-07-14 21:21:15 on Problem 2502
一个double想当然地习惯打成int导致精度缺失= =debug了半天WA了好几次。。。
然后最蠢的是删调试信息删错行了导致死循环TLE了一次。。。真是醉了!
#include <iostream>
#include <map>
#include <cmath>
#include <stdio.h>
#include <iomanip>
using namespace std;

const int home = 0;
const int school = 1;
const double MAX = 1e16;

class point{
public:
	int x;
	int y;
	point(int x, int y): x(x), y(y){}
	point(): x(0), y(0){}
};

bool operator<(const point& p1, const point& p2){
	if(p1.x < p2.x) return true;
	if(p1.x > p2.x) return false;
	return p1.y < p2.y;
}

point stats[210];

double jl[210][210];

map<point, int> mmp;

double dist(point& p1, point& p2){
	return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) + 0.0);
}

int main() {
	int homex, homey, schoolx, schooly;
	scanf("%d%d%d%d", &homex, &homey, &schoolx, &schooly);
	stats[0].x = homex;
	stats[0].y = homey;
	stats[1].x = schoolx;
	stats[1].y = schooly;
	mmp.insert(pair<point, int>(stats[0], 0));
	mmp.insert(pair<point, int>(stats[1], 1));
	int curx, cury, oldx, oldy, curno, oldno;
	int no = 2;
	for(int i = 0; i < 210; i++){
		for(int j = 0; j < 210; j++){
			if(i == j) jl[i][j] = 0;
			else jl[i][j] = MAX;
		}
	}
	while(cin >> oldx >> oldy){
		if(oldx == -1 && oldy == -1) break;
		//point tempP = point(oldx, oldy);
		map<point, int>::iterator it = mmp.find(point(oldx, oldy));
		if(it != mmp.end()){
			oldno = it->second;
		}
		else{
			mmp.insert(pair<point, int>(point(oldx, oldy), no));
			stats[no].x = oldx;
			stats[no].y = oldy;
			oldno = no;
			no++;
		}
		while(1){
			cin >> curx >> cury;
			if(curx == -1 && cury == -1) break;
			map<point, int>::iterator it = mmp.find(point(curx, cury));
			if(it != mmp.end()){
				curno = it->second;
			}
			else{
				mmp.insert(pair<point, int>(point(curx, cury), no));
				stats[no].x = curx;
				stats[no].y = cury;
				curno = no;
				no++;
			}
			jl[oldno][curno] = dist(stats[oldno], stats[curno]) / 4;
			//cout << jl[oldno][curno] << endl;
			jl[curno][oldno] = jl[oldno][curno];
			oldno = curno;
			oldx = curx;
			oldy = cury;
		}
	}
	//cout << no << endl;
	/*
	for(int i = 0; i < no; i++){
		cout << stats[i].x << " " << stats[i].y << endl;
	}*/
	for(int i = 0; i < no; i++){
		for(int j = 0; j < no; j++){
			if(i != j && jl[i][j] >= MAX/10){
				jl[i][j] = dist(stats[i], stats[j]);
			}
		}
	}
	/*
	for(int i = 0; i < no; i++){
		for(int j = 0; j < no; j++){
			cout << jl[i][j] << " ";
		}
		cout << endl;
	}
	*/
	bool state[210] = {true, false};
	double dists[210] = {0};
	double addDists[210] = {0};
	int arg[210] = {0};
	for(int i = 1; i < no; i++) dists[i] = MAX;
	for(int i = 1; i < no; i++) addDists[i] = MAX;
	int added = 0;
	while(1){
		for(int i = 1; i < no; i++){
			if(state[i]) continue;
			double newDist = dists[added] + jl[added][i];
			if(newDist < addDists[i]){
				addDists[i] = newDist;
				arg[i] = added;
			}
		}
		int tobeAdded;
		double MIN = MAX;
		for(int i = 1; i < no; i++){
			if(state[i]) continue;
			if(addDists[i] < MIN){
				MIN = addDists[i];
				tobeAdded = i;
			}
		}
		dists[tobeAdded] = MIN;
		if(tobeAdded == school){
			break;
		}
		state[tobeAdded] = true;
		added = tobeAdded;
	}
	double t = dists[school] * 0.006;
	//cout << setprecision(32) << t << endl;
	int tint = (int)t;
	if(t - tint < 0.5) cout << tint;
	else cout << tint+1;
	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