Advertisement
YauhenMardan

Untitled

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