Cod sursa(job #2225986)

Utilizator mgntMarius B mgnt Data 28 iulie 2018 23:49:56
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 24.38 kb
                                                                             
#define FOLD__SCOPE                                                          
                                                                             
#ifdef  FOLD__SCOPE  /// includes                                            
                                                                             
#include <cstddef>                                                           
#include <vector>                                                            
#include <algorithm>                                                         
#include <fstream>                                                           
#include <sstream>                                                           
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// typedefs                                            
                                                                             
typedef  ::std::size_t     stsz;                                             
typedef  long long signed  stws;                                             
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// point                                               
                                                                             
struct ptst                                                                  
{                                                                            
  stws  x;                                                                   
  stws  y;                                                                   
                                                                             
  ptst () noexcept : x(0), y(0) {  }                                         
                                                                             
};                                                                           
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// comparator                                          
                                                                             
bool                                                                         
dnlt                                                                         
(                                                                            
  ptst const  & A                                                            
, ptst const  & B                                                            
)                                                                            
noexcept                                                                     
{                                                                            
  return (A.y == B.y) ? (A.x > B.x) : (A.y > B.y);                           
}                                                                            
                                                                             
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// typedefs                                            
                                                                             
typedef  ::std::vector < ptst >  vtpt;                                       
                                                                             
typedef  ::std::ifstream      stis;                                          
typedef  ::std::ofstream      stos;                                          
typedef  ::std::stringstream  stss;                                          
                                                                             
typedef  ::std::string  stsg;                                                
                                                                             
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// input                                               
                                                                             
bool                                                                         
read_input                                                                   
(                                                                            
  vtpt  & P                                                                  
)                                                                            
{                                                                            
  stsz  const min_n = 1;                                                     
  stsz  const max_n = 1000;                                                  
  stws  const min_v = -99999999;                                             
  stws  const max_v =  99999999;                                             
                                                                             
  stis  is ("patrate3.in");                                                  
  stsg  il;                                                                  
  stss  ss;                                                                  
                                                                             
  getline(is, il);                                                           
  ss << il << '\n';                                                          
                                                                             
  stsz  n = 0;                                                               
  ss >> n;                                                                   
                                                                             
  bool  ok = false;                                                          
                                                                             
  ok = ( (min_n <= n) && (max_n >= n)  );                                    
                                                                             
  if ( ! ok  )                                                               
  {                                                                          
    /// Invalid input.                                                       
    return false;                                                            
  }                                                                          
                                                                             
  vtpt  p(n);                                                                
                                                                             
  stsz  i = 0;                                                               
  stsz  s = 0;                                                               
  stws  x = 0;                                                               
  stws  y = 0;                                                               
                                                                             
  ptst  z;                                                                   
                                                                             
  for ( i = 0; n > i; ++ i  )                                                
  {                                                                          
    getline(is, il);                                                         
                                                                             
                                                                             
    s = il.find('.');                                                        
                                                                             
    ok = ( ( ::std::string::npos) != s );                                    
                                                                             
    if ( ! ok  )                                                             
    {                                                                        
      /// Failure.  The called logged.                                       
      return false;                                                          
    }                                                                        
                                                                             
    il.erase(s, 1);                                                          
                                                                             
                                                                             
    s = il.find('.');                                                        
                                                                             
    ok = ( ( ::std::string::npos) != s );                                    
                                                                             
    if ( ! ok  )                                                             
    {                                                                        
      /// Failure.  The called logged.                                       
      return false;                                                          
    }                                                                        
                                                                             
    il.erase(s, 1);                                                          
                                                                             
                                                                             
    ss << il << '\n';                                                        
                                                                             
    ss >> x >> y;                                                            
                                                                             
    ok = ( (min_v <= x) && (max_v >= x) &&                                   
           (min_v <= y) && (max_v >= y)     );                               
                                                                             
    if ( ! ok  )                                                             
    {                                                                        
      /// Invalid input.                                                     
      return false;                                                          
    }                                                                        
                                                                             
    z.x = x;                                                                 
    z.y = y;                                                                 
                                                                             
    p[i] = z;                                                                
                                                                             
  }                                                                          
                                                                             
  ::std::sort(p.begin(), p.end(), dnlt);                                     
                                                                             
  for ( i = 0; n-1 > i; ++ i  )                                              
  {                                                                          
    ok = (  ( p[i].x != p[1+i].x) || (p[i].y != p[1+i].y)  );                
                                                                             
    if ( ! ok  )                                                             
    {                                                                        
      /// Invalid input.                                                     
      return false;                                                          
    }                                                                        
                                                                             
  }                                                                          
                                                                             
  /// Excelent!                                                              
                                                                             
  P.swap(p);                                                                 
                                                                             
  return true;                                                               
                                                                             
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// search                                              
                                                                             
bool                                                                         
side                                                                         
(                                                                            
  vtpt  const      & P                                                       
, stsz         const i                                                       
, stsz         const j                                                       
)                                                                            
{                                                                            
                                                                             
  if ( ( P[i].y >  P[j].y ) &&                                               
       ( P[i].x <= P[j].x )     )                                            
  {                                                                          
    return false;                                                            
  }                                                                          
                                                                             
                                                                             
  ptst const  & A = P[i];                                                    
  ptst const  & B = P[j];                                                    
                                                                             
  stws  const xD = (A.x) + ((A.y) - (B.y));                                  
  stws  const yD = (A.y) + ((B.x) - (A.x));                                  
                                                                             
  ptst  D;                                                                   
  D.x = xD;                                                                  
  D.y = yD;                                                                  
                                                                             
                                                                             
  bool  found = false;                                                       
                                                                             
  found = ::std::binary_search(P.begin(), P.end(), D, dnlt);                 
                                                                             
  if ( ! found  )                                                            
  {                                                                          
    return false;                                                            
  }                                                                          
                                                                             
                                                                             
  stws  const xC = (D.x) + ((D.y) - (A.y));                                  
  stws  const yC = (D.y) + ((A.x) - (D.x));                                  
                                                                             
  ptst  C;                                                                   
  C.x = xC;                                                                  
  C.y = yC;                                                                  
                                                                             
  found = ::std::binary_search(P.begin(), P.end(), C, dnlt);                 
                                                                             
  return found;                                                              
                                                                             
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// solve                                               
                                                                             
stsz                                                                         
count                                                                        
(                                                                            
  vtpt const  & P                                                            
)                                                                            
{                                                                            
  stsz  const n = P.size();                                                  
                                                                             
  stsz  i = 0;                                                               
  stsz  j = 0;                                                               
  bool  s = 0;                                                               
  stsz  k = 0;                                                               
                                                                             
  for ( i = 0; n > i; ++ i )                                                 
  {                                                                          
    for ( j = 1 + i; n > j; ++ j  )                                          
    {                                                                        
      s = side(P, i, j);                                                     
      k = s ? (1 + k) : k;                                                   
    }                                                                        
                                                                             
  }                                                                          
                                                                             
  return k;                                                                  
                                                                             
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// output                                              
                                                                             
void                                                                         
write_output                                                                 
(                                                                            
  stsz  const answer                                                         
)                                                                            
{                                                                            
  stos  os("patrate3.out");                                                  
  os << answer << '\n';                                                      
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// demo                                                
                                                                             
bool                                                                         
demo                                                                         
()                                                                           
{                                                                            
  vtpt  P;                                                                   
  stsz  a = 0;                                                               
                                                                             
  bool  ok = false;                                                          
                                                                             
  ok = read_input(P);                                                        
                                                                             
  if ( ! ok  )                                                               
  {                                                                          
    return false;                                                            
  }                                                                          
                                                                             
  a = count(P);                                                              
                                                                             
  write_output(a);                                                           
                                                                             
  return true;                                                               
                                                                             
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// main                                                
                                                                             
int                                                                          
main                                                                         
()                                                                           
{                                                                            
  int  status = 2;                                                           
                                                                             
  try                                                                        
  {                                                                          
    bool  const ok = demo();                                                 
    status = ( ok ? 0 : 1 );                                                 
  }                                                                          
  catch ( ... )                                                              
  {                                                                          
    status = 3;                                                              
  }                                                                          
                                                                             
  return status;                                                             
                                                                             
}                                                                            
                                                                             
#endif