YauhenMardan

Untitled

Mar 14th, 2019
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.42 KB | None | 0 0
  1. #include <fstream>
  2. #include <algorithm>
  3. #include <iostream>
  4.  
  5. class Bush{
  6. public:
  7. int x,y;
  8. };
  9.  
  10. int max(int a,int b);
  11. bool compare(Bush a,Bush b);
  12. bool isOut(int x,int y, int r,int c);
  13. int countPath(Bush bush, int distX,int distY,int r,int c);
  14.  
  15. bool** bushesField;
  16.  
  17. void foo(int i);
  18.  
  19. int main(int argc, const char * argv[]) {
  20. for(int i=11;i<25;i++){
  21. foo(i);
  22. }
  23. return 0;
  24. }
  25. void foo(int i){
  26. std::ifstream fin("frog."+std::to_string(i)+".in");
  27. std::ifstream finA("frog."+std::to_string(i)+".sol");
  28. Bush* bushes;
  29. int r,c;
  30. int n;
  31. fin>>r;
  32. fin>>c;
  33. fin>>n;
  34. //read
  35. int x,y;
  36. bushes=new Bush[n];
  37. bushesField=new bool*[r+1];
  38. for(int i=0;i<r+1;i++){
  39. bushesField[i]=new bool[c+1];
  40. for(int j=0;j<c+1;j++){
  41. bushesField[i][j]=0;
  42. }
  43. }
  44. for(int i=0;i<n;i++){
  45. fin>>x;
  46. fin>>y;
  47. bushes[i].x=x;
  48. bushes[i].y=y;
  49. bushesField[x][y]=1;
  50. }
  51. //sort
  52. std::sort(bushes, bushes+n, compare);
  53. //algo
  54. int distX,distY,nextX,nextY;
  55. int maxPath=2;
  56. for(int i=0;i<n-1;i++){
  57. for(int j=i+1; j<n;j++){
  58. distX=bushes[j].x-bushes[i].x;
  59. distY=bushes[j].y-bushes[i].y;
  60. nextX=bushes[i].x+distX*maxPath;
  61. nextY=bushes[i].y+distY*maxPath;
  62. if(nextX > r){
  63. break;
  64. }
  65. if(isOut(bushes[i].x-distX, bushes[i].y-distY,r,c)){
  66. continue;
  67. }
  68. if(!isOut(nextX, nextY,r,c)){
  69. continue;
  70. }
  71. maxPath=max(countPath(bushes[i],distX,distY,r,c),maxPath);
  72. }
  73. }
  74. std::cout<<"My:\n";
  75. if(maxPath<3){
  76. std::cout<<0<<"\n";
  77. } else{
  78. std::cout<<maxPath<<"\n";
  79. }
  80. int a;
  81. finA>>a;
  82. std::cout<<"Ans:\n"<<a<<"\n\n";
  83. }
  84.  
  85. bool compare(Bush a,Bush b){
  86. if(a.x==b.x){
  87. return a.y<b.y;
  88. }
  89. return a.x<b.x;
  90. }
  91.  
  92. bool isOut(int x,int y, int r,int c){
  93. return (0 < x && x < r+1 && 0 < y && y < c+1);
  94. }
  95. int countPath(Bush bush, int distX,int distY,int r,int c){
  96. int path=0;
  97. while(isOut(bush.x, bush.y, r, c)){
  98. if(!bushesField[bush.x][bush.y]){
  99. return 0;
  100. }
  101. bush.x+=distX;
  102. bush.y+=distY;
  103. path++;
  104. }
  105. return path;
  106. }
  107.  
  108. int max(int a,int b){
  109. return a<b ? b : a;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment