Advertisement
a53

piscina

a53
Jul 28th, 2017
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. /*
  2. Complexitate timp: O(PlogP)
  3. 100 puncte
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #define PMax 100005
  9.  
  10. FILE *fin = fopen("piscina.in", "rt");
  11. FILE *fout = fopen("piscina.out", "wt");
  12.  
  13. int n, m, p;
  14. typedef struct point {
  15. int x, y;
  16. } point;
  17.  
  18. point c[PMax];
  19.  
  20. int compY(const void *a, const void *b);
  21. long long detMax() {
  22. qsort(c, p, sizeof(c[0]), compY);
  23. int prev = 0;
  24. long long aMax = 0, area;
  25. for (int i = 1; i < p; i++) {
  26. if (c[i].x < c[prev].x) {
  27. area = c[prev].x;
  28. area *= c[i].y;
  29. prev = i;
  30. if (aMax < area) {
  31. aMax = area;
  32. }
  33. }
  34. }
  35. return aMax;
  36. }
  37.  
  38. int compY(const void *a, const void *b) {
  39. return ((point *) a) -> y - ((point *) b) -> y;
  40. }
  41.  
  42. void mirror(point *c, int N, int M) {
  43. for (int i = 0; i < p; i++) if (c[i].x && c[i].y) {
  44. if (N > 0) {
  45. c[i].x = N - c[i].x;
  46. }
  47. if (M > 0) {
  48. c[i].y = M - c[i].y;
  49. }
  50. }
  51. }
  52.  
  53. int main() {
  54.  
  55. fscanf(fin, "%d %d %d", &n, &m, &p);
  56. for (int i = 0; i < p; i++) {
  57. fscanf(fin, "%d %d", &c[i].x, &c[i].y);
  58. }
  59. c[p].x = 0; c[p].y = m;
  60. c[p + 1].x = n; c[p + 1].y = 0;
  61. p += 2;
  62.  
  63. long long aMax = 0, area;
  64. area = detMax(); if (aMax < area) { aMax = area; }
  65. mirror(c, n, 0);
  66. area = detMax(); if (aMax < area) { aMax = area; }
  67. mirror(c, 0, m);
  68. area = detMax(); if (aMax < area) { aMax = area; }
  69. mirror(c, n, 0);
  70. area = detMax(); if (aMax < area) { aMax = area; }
  71.  
  72. fprintf(fout, "%lld\n", aMax);
  73. fclose(fin);
  74. fclose(fout);
  75.  
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement