Guest User

Untitled

a guest
Nov 18th, 2012
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <set>
  8. #include <memory.h>
  9. #include <map>
  10. #include <math.h>
  11. #include <queue>
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. #include <string>
  15. #include <iostream>
  16. #include <algorithm>
  17. #include <vector>
  18. #include <set>
  19. #include <memory.h>
  20. #include <map>
  21. #include <math.h>
  22. #include <queue>
  23. #include <stack>
  24. #include <complex>
  25. #include <list>
  26. #include <deque>
  27. #pragma comment(linker, "/STACK:16777216") // SET_STACKSIZE_16MB
  28. using namespace std;
  29.  
  30. #ifdef WIN32
  31.     #define LLD "%I64d"
  32. #else
  33.     #define LLD "%lld"
  34. #endif
  35.  
  36. typedef long long ll;
  37. typedef unsigned long long ull;
  38.  
  39. const long double PI = acos(-1.0);
  40. const double eps = 1e-12;
  41. const int INF = 2147483647;
  42. const ll LLINF = 9223372036854775807LL;
  43. const int MAXPRIMES = 3163; // 3163 = sqrt(10^9) (FOR GENPRIMES)
  44. const int MAXSIZESTR = 110; // FOR GEN_HASH
  45. const int BASE = 31;
  46. const ll MOD = 1000000073;
  47. const ll MAXN = 100010;
  48.  
  49. #define mp make_pair
  50. #define pb push_back
  51. #define sz(x) (int)x.size()
  52. #define X first
  53. #define Y second
  54. #define all(x) x.begin(),x.end()
  55.  
  56. struct lenStruct {
  57.     ll left,right;
  58.     ll cnt, color;
  59.     double resColor;
  60.     lenStruct(int left1, int right1, int cnt1, int color1, double resColor1) : left(left1), right(right1), cnt(cnt1), color(color1), resColor(resColor1) {}
  61.     lenStruct() : left(LLINF), right(-1), cnt(0), color(0), resColor(0.) {}
  62. };
  63.  
  64. int n;
  65. vector<lenStruct> piece;
  66. bool can[100010] = {false};
  67.  
  68. int main()
  69. {
  70.     freopen("painting.in", "rt", stdin);
  71.     freopen("painting.out", "wt", stdout);
  72.     //freopen("input.txt", "r", stdin);
  73.     //freopen("output.txt", "w", stdout);
  74.    
  75.     scanf("%d", &n);
  76.     for (int i = 0; i < n; i++) {
  77.         ll l,r,c;
  78.         scanf(LLD LLD LLD, &l,&r,&c);
  79.         int kk = 0;
  80.         double maxVal = 0;
  81.         lenStruct newPiece (lenStruct(l,r,1,c,c+0.));
  82.         bool flag = false;
  83.         for (vector<lenStruct>::iterator j = piece.begin(); j != piece.end(); j++, kk++) {
  84.             if (!can[kk]) {
  85.                 if (l < (*j).left && r > (*j).left) {
  86.                     can[kk] = true;
  87.                     newPiece.right = max(newPiece.right, (*j).right);
  88.                     newPiece.left = min(newPiece.left, (*j).left);
  89.                     newPiece.color += (*j).color;
  90.                     newPiece.cnt += (*j).cnt;
  91.                     flag = true;
  92.                     continue;
  93.                 }
  94.                 else {
  95.                     if (r > (*j).right && l < (*j).right) {
  96.                         can[kk] = true;
  97.                         newPiece.right = max(newPiece.right, (*j).right);
  98.                         newPiece.left = min(newPiece.left, (*j).left);
  99.                         newPiece.color += (*j).color;
  100.                         newPiece.cnt += (*j).cnt;
  101.                         flag = true;
  102.                         continue;
  103.                     }
  104.                     else {
  105.                         if (l >= (*j).left && r <= (*j).right) {
  106.                             can[kk] = true;
  107.                             newPiece.right = max(newPiece.right, (*j).right);
  108.                             newPiece.left = min(newPiece.left, (*j).left);
  109.                             newPiece.color += (*j).color;
  110.                             newPiece.cnt += (*j).cnt;
  111.                             flag = true;
  112.                             continue;
  113.                         }
  114.                     }
  115.                 }
  116.                 maxVal = max(maxVal, (*j).resColor);
  117.             }
  118.         }
  119.         if (flag) newPiece.resColor = (newPiece.color+0.) / newPiece.cnt;
  120.         maxVal = max(maxVal, newPiece.resColor);
  121.         piece.pb(newPiece);
  122.         printf("%.6f\n", maxVal);
  123.     }
  124.  
  125.     return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment