Advertisement
YauhenMardan

Untitled

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