| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
真是惨。。。(附代妈)一个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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator