Advertisement
Guest User

triangoli.cpp

a guest
Aug 21st, 2014
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.75 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <deque>
  4.  
  5. using namespace std;
  6.  
  7. struct Point {
  8.     long double x,y;
  9. //  char c;
  10. };
  11.  
  12. int func(deque<Point> p){
  13.    
  14.     int out = 0;
  15.    
  16.     // cerco il punto che sta più in basso e a parità di y quello più a destra
  17.     int minY = 0;
  18.     for(int i=1; i<p.size(); i++)
  19.         if(p[i].y < p[minY].y || (p[i].y == p[minY].y && p[i].x > p[minY].x))
  20.             minY = i;
  21. //  printf("%c\n\n\n", p[minY].c);
  22.    
  23.     int ok,ok2;
  24.     double angle;
  25.    
  26.     // salvo le coordinate del punto
  27.     long double x = p[minY].x, y = p[minY].y;
  28.    
  29.     // salvo il primo punto
  30.     struct Point primo = p[minY];
  31.     // elimino il primo punto
  32.     p.erase(p.begin()+minY);
  33.    
  34.     // primo ciclo
  35.     do{
  36.         ok = -1;
  37.         ok2 = -1;
  38.        
  39.         for(int i=0; i<p.size(); i++)
  40.             if(x != p[i].x){
  41.                
  42.                 double a = (double)(p[i].y-y)/(p[i].x-x);
  43.                
  44.                 if(a>0 && x<p[i].x){
  45.                     if(ok == -1){
  46.                         ok = i;
  47.                         angle = a;
  48.                     }
  49.                     else{
  50.                         if(a < angle){
  51.                             ok = i;
  52.                             angle = a;
  53.                         }
  54.                         else
  55.                             if(a == angle)
  56.                                 if(p[i].x > p[ok].x)
  57.                                     ok = i;
  58.                     }
  59.                 }
  60.             }
  61.             else{
  62.                 if(ok == -1){
  63.                     if(ok2 == -1)
  64.                         ok2 = i;
  65.                     else
  66.                         if(p[ok2].y > p[i].y)
  67.                             ok2 = i;
  68.                 }
  69.             }
  70.        
  71.         if(ok != -1){
  72.             out++;
  73.             x = p[ok].x;
  74.             y = p[ok].y;
  75. //          printf("%c\n", p[ok].c);
  76.             p.erase(p.begin()+ok);
  77.         }
  78.         else
  79.             if(ok2 != -1){
  80.                 out++;
  81.                 x = p[ok2].x;
  82.                 y = p[ok2].y;
  83. //              printf("%c\n", p[ok2].c);
  84.                 p.erase(p.begin()+ok2);
  85.             }
  86.        
  87.     }while(ok != -1);
  88.    
  89.     // secondo ciclo
  90.     do{
  91.         ok = -1;
  92.         ok2 = -1;
  93.        
  94.         for(int i=0; i<p.size(); i++)
  95.             if(x != p[i].x)
  96.                 if(y != p[i].y){
  97.                    
  98.                     double a = (double)(p[i].y-y)/(p[i].x-x);
  99.                    
  100.                     if(a<0 && x>p[i].x){
  101.                         if(ok == -1){
  102.                             ok = i;
  103.                             angle = a;
  104.                         }
  105.                         else{
  106.                             if(a < angle){
  107.                                 ok = i;
  108.                                 angle = a;
  109.                             }
  110.                             else
  111.                                 if(a == angle)
  112.                                     if(p[i].x < p[ok].x)
  113.                                         ok = i;
  114.                         }
  115.                     }
  116.                 }
  117.                 else{
  118.                     if(ok == -1){
  119.                         if(ok2 == -1)
  120.                             ok2 = i;
  121.                         else
  122.                             if(p[ok2].x > p[i].x)
  123.                                 ok2 = i;
  124.                     }
  125.                 }
  126.        
  127.        
  128.         if(ok != -1){
  129.             out++;
  130.             x = p[ok].x;
  131.             y = p[ok].y;
  132. //          printf("%c\n", p[ok].c);
  133.             p.erase(p.begin()+ok);
  134.         }
  135.         else
  136.             if(ok2 != -1){
  137.                 out++;
  138.                 x = p[ok2].x;
  139.                 y = p[ok2].y;
  140. //              printf("%c\n", p[ok2].c);
  141.                 p.erase(p.begin()+ok2);
  142.             }
  143.    
  144.     }while(ok != -1);
  145.    
  146.     // rimetto il primo punto nella lista per poter chiudere il cerchio
  147.     p.push_back(primo);
  148.    
  149.     // terzo ciclo
  150.     do{    
  151.         ok = -1;
  152.         ok2 = -1;
  153.        
  154.         for(int i=0; i<p.size(); i++)
  155.             if(x != p[i].x){
  156.                
  157.                 double a = (double)(p[i].y-y)/(p[i].x-x);
  158.                
  159.                 if(a>0 && x>p[i].x){
  160.                     if(ok == -1){
  161.                         ok = i;
  162.                         angle = a;
  163.                     }
  164.                     else{
  165.                         if(a < angle){
  166.                             ok = i;
  167.                             angle = a;
  168.                         }
  169.                         else
  170.                             if(a == angle)
  171.                                 if(p[i].x < p[ok].x)
  172.                                     ok = i;
  173.                     }
  174.                 }
  175.             }
  176.             else{
  177.                 if(ok == -1){
  178.                     if(ok2 == -1)
  179.                         ok2 = i;
  180.                     else
  181.                         if(p[ok2].y > p[i].y)
  182.                             ok2 = i;
  183.                 }
  184.             }
  185.        
  186.         if(ok != -1){
  187.             out++;
  188.             x = p[ok].x;
  189.             y = p[ok].y;
  190. //          printf("%c\n", p[ok].c);
  191.             p.erase(p.begin()+ok);
  192.         }
  193.         else
  194.             if(ok2 != -1){
  195.                 out++;
  196.                 x = p[ok2].x;
  197.                 y = p[ok2].y;
  198. //              printf("%c\n", p[ok2].c);
  199.                 p.erase(p.begin()+ok2);
  200.             }
  201.    
  202.     }while(ok != -1);
  203.    
  204.     // quarto e ultimo ciclo
  205.     do{
  206.         ok = -1;
  207.         ok2 = -1;
  208.        
  209.         for(int i=0; i<p.size(); i++)
  210.             if(x != p[i].x)
  211.                 if(y != p[i].y){
  212.                    
  213.                     double a = (double)(p[i].y-y)/(p[i].x-x);
  214.                    
  215.                     if(a<0 && x<p[i].x){
  216.                         if(ok == -1){
  217.                             ok = i;
  218.                             angle = a;
  219.                         }
  220.                         else{
  221.                             if(a < angle){
  222.                                 ok = i;
  223.                                 angle = a;
  224.                             }
  225.                             else
  226.                                 if(a == angle)
  227.                                     if(p[i].x > p[ok].x)
  228.                                         ok = i;
  229.                         }
  230.                     }
  231.                 }
  232.                 else{
  233.                     if(ok == -1){
  234.                         if(ok2 == -1)
  235.                             ok2 = i;
  236.                         else
  237.                             if(p[ok2].y > p[i].y)
  238.                                 ok2 = i;
  239.                     }
  240.                 }
  241.        
  242.     if(ok != -1){
  243.         out++;
  244.         x = p[ok].x;
  245.         y = p[ok].y;
  246. //      printf("%c\n", p[ok].c);
  247.         p.erase(p.begin()+ok);
  248.     }
  249.     else
  250.         if(ok2 != -1){
  251.             out++;
  252.             x = p[ok2].x;
  253.             y = p[ok2].y;
  254. //          printf("%c\n", p[ok2].c);
  255.             p.erase(p.begin()+ok2);
  256.         }
  257.    
  258.    
  259.     }while(ok != -1);
  260.    
  261.     return out;
  262. }
  263.  
  264. main(){
  265.     FILE *pF = fopen("input.txt", "r");
  266.     int n;
  267.     fscanf(pF, "%d", &n);
  268.     int i;
  269.     deque<Point> p;
  270.     struct Point x;
  271.     int a,b;
  272.     for(i=0; i<n; i++){
  273.         fscanf(pF, "\n%d %d", &a, &b);
  274.         x.x = (long double)a;
  275.         x.y = (long double)b;
  276. //      x.c = 'a'+i;
  277.         p.push_back(x);
  278.     }
  279.     if(p.size()<4)
  280.         return 123;
  281.     int ris = func(p);
  282. //  printf("%d", ris);
  283.     FILE *pF2 = fopen("output.txt", "w");
  284.     fprintf(pF2, "%d", ris);
  285.     fclose(pF2);   
  286. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement