Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Apr 29th, 2012  |  syntax: C++  |  size: 3.15 KB  |  hits: 23  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<stdio.h>
  2. #define inf "puncte.in"
  3. #define outf "puncte.out"
  4. #define nmax 10010
  5. #define INF 0x3f3f3f3f
  6. using namespace std;
  7.  
  8.  
  9. const double eps = 1e-10;
  10.  
  11. int n;
  12.  
  13. struct point {
  14.         int x, y;
  15. } A, B, p[nmax]; //punctele de baza si lista punctelor conventionale
  16.  
  17. void read()
  18. {
  19.         scanf("%d%d%d%d%d", &n, &A.x, &A.y, &B.x, &B.y);
  20.        
  21.         for(int i=1; i<=n; i++) scanf("%d%d", &p[i].x, &p[i].y);
  22. }
  23.  
  24. inline int max(int a, int b) { return a>b ? a : b; }
  25.  
  26. void solve()
  27. {
  28.         int ans = -INF;
  29.         //unesc punctul de baza A cu punctul conventional i => obtin dreapta de panta m
  30.         for(int i=1; i<=n; i++) {              
  31.                 double m;
  32.                 if( A.x == p[i].x ) m = INF; //dreapta perpendiculara pe OX
  33.                 else m = (double)( (A.y-p[i].y) * (1.0) ) / (double) ((A.x-p[i].x)*1.0);
  34.                                
  35.                 if( m==INF ) {  //dreapta perpendiculara pe OX ( e simplu :D )         
  36.                         //verific cate puncte se incadreaza intre cele doua drepte perpendiculare pe OX date de A si B
  37.                         int rez = 0;
  38.                         for(int j=1; j<=n; j++)
  39.                                 if( ( p[j].x>=A.x && p[j].x<=B.x ) || ( p[j].x>=B.x && p[j].x<=A.x ) ) rez++;
  40.                         ans = max( ans, rez );
  41.                         continue;
  42.                 }
  43.                
  44.                 //ecuatiile dreptelor d1 : a1*x + b1*y + c1 = 0 (trece prin A) si d2 : a2*x + b2*y + c2 = 0 (trece prin B)
  45.                 // d1 || d2
  46.                 double a1, b1, c1; double a2, b2, c2;
  47.                 a1 = m; b1 = -1; c1 = -A.y-m*A.x;
  48.                 a2 = m; b2 = -1; c2 = -B.y-m*B.x;
  49.                 //printf("%lf %lf %lf\n", a1, b1, c1);
  50.                
  51.                 //verific cate puncte sunt intre d1 si d2
  52.                 int rez = 0;
  53.                 for(int j=1; j<=n; j++) {
  54.                         double y1 = -(a1/b1)*(double)( (1.0)*p[j].x ) - (c1/b1);
  55.                         double y2 = -(a2/b2)*(double)( (1.0)*p[j].x ) - (c2/b2);
  56.                        
  57.                         //printf("%lf %lf\n", y1, y2);
  58.                          
  59.                         if( ( p[j].y<=y1 && p[j].y>=y2 ) || ( p[j].y<=y2 && p[j].y>=y1 ) ) rez++;
  60.                 }
  61.                 //printf("\n");
  62.                 ans = max( ans, rez );
  63.         }
  64.        
  65.         //unesc punctul de baza B cu punctul conventional i => obtin dreapta de panta m
  66.         for(int i=1; i<=n; i++) {
  67.                 double m;
  68.                 if( B.x == p[i].x ) m = INF; //dreapta perpendiculara pe OX
  69.                 else m = (double)( (B.y-p[i].y) * (1.0) ) / (double) ((B.x-p[i].x)*1.0);
  70.                
  71.                 if( m==INF ) {  //dreapta perpendiculara pe OX ( e simplu :D )         
  72.                         //verific cate puncte se incadreaza intre cele doua drepte perpendiculare pe OX date de A si B
  73.                         int rez = 0;
  74.                         for(int j=1; j<=n; j++)
  75.                                 if( ( p[j].x>=A.x && p[j].x<=B.x ) || ( p[j].x>=B.x && p[j].x<=A.x ) ) rez++;
  76.                         ans = max( ans, rez );
  77.                         continue;
  78.                 }
  79.                
  80.                 //ecuatiile dreptelor d1 : a1*x + b1*y + c1 = 0 (trece prin B) si d2 : a2*x + b2*y + c2 = 0 (trece prin A)
  81.                 // d1 || d2
  82.                 double a1, b1, c1; double a2, b2, c2;
  83.                 a2 = m; b2 = -1; c2 = -A.y-m*A.x;
  84.                 a1 = m; b1 = -1; c1 = -B.y-m*B.x;
  85.                 //printf("%lf %lf %lf\n", a1, b1, c1);
  86.                
  87.                 //verific cate puncte sunt intre d1 si d2
  88.                 int rez = 0;
  89.                 for(int j=1; j<=n; j++) {
  90.                         double y1 = -(a1/b1)*(double)( (1.0)*p[j].x ) - (c1/b1);
  91.                         double y2 = -(a2/b2)*(double)( (1.0)*p[j].x ) - (c2/b2);
  92.                        
  93.                         //printf("%lf %lf\n", y1, y2);
  94.                          
  95.                         if( ( p[j].y<=y1 && p[j].y>=y2 ) || ( p[j].y<=y2 && p[j].y>=y1 ) ) rez++;
  96.                 }
  97.                 //printf("\n");
  98.                 ans = max( ans, rez );
  99.         }
  100.        
  101.         printf("%d", ans);
  102. }
  103.  
  104. int main()
  105. {
  106.         freopen(inf, "r", stdin); freopen(outf, "w", stdout);
  107.         read(); solve();
  108.         return 0;
  109. }
create a new version of this paste RAW Paste Data