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