Advertisement
Guest User

Untitled

a guest
Sep 12th, 2012
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include<cmath>
  4.  
  5. using namespace std;
  6.  
  7. struct point{
  8.      int x,y;
  9. };
  10.  
  11. int main(){
  12.     int N,M,diagnum = 0;
  13.     cin >> N >> M;
  14.     double ans = (N+M)*100;
  15.     int num;
  16.     cin >> num;
  17.     vector< point > diag(num);
  18.     for(int i = 0; i < num; ++i){
  19.         cin >> diag[i].x >> diag[i].y;
  20.         --diag[i].x;
  21.         --diag[i].y;
  22.     }
  23.     point CurPos;
  24.     CurPos.x = 0, CurPos.y = 0;
  25.     while(CurPos.x != N && CurPos.y != M){
  26.         bool exists = false;
  27.         int minim = 1e9,minnum;
  28.         for(int i = 0; i < num; ++i){
  29.             if((diag[i].x != -1) && (diag[i].y != -1) && (diag[i].x >= CurPos.x) && (diag[i].y >= CurPos.y)  && ((diag[i].x - CurPos.x + diag[i].y - CurPos.y) < minim)){
  30.                 minnum = i;
  31.                 minim = diag[i].x - CurPos.x + diag[i].y - CurPos.y;
  32.                 exists = true;
  33.             }
  34.         }
  35.         if(exists){
  36.             CurPos.x = diag[minnum].x+1;
  37.             CurPos.y = diag[minnum].y+1;
  38.             diag[minnum].x = diag[minnum].y = - 1;
  39.             ++diagnum;
  40.         }
  41.         else{
  42.             CurPos.x = N;
  43.             CurPos.y = M;
  44.         }
  45.     }
  46.     ans-=diagnum*100*(2 - sqrt(2.0));
  47.     double intpart;
  48.     ans = (modf (ans , &intpart) >= 0.5 ? ceil(ans) : floor(ans));
  49.     cout << ans << endl;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement