Advertisement
Guest User

Untitled

a guest
Mar 7th, 2012
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.17 KB | None | 0 0
  1. #include "stdio.h"
  2. #include "assert.h"
  3. #include "stdlib.h"
  4.  
  5. #include <iostream>
  6. #include <bitset>
  7.  
  8. using namespace std;
  9.  
  10. #define MPOUFOS (14*1024*1024)
  11.  
  12. class dianysma{
  13.     public:
  14.    
  15.     int x;
  16.     int y;
  17.     int arx_id;
  18.     dianysma();
  19.     dianysma(int,int);
  20.     dianysma(const dianysma &);
  21.     dianysma &operator=(const dianysma &);
  22.     dianysma operator+(dianysma);
  23.     dianysma operator-(dianysma);
  24.     int operator^(dianysma);
  25. };
  26. dianysma::dianysma(){
  27.    
  28. }
  29. dianysma::dianysma(int a, int b){
  30.     x=a;
  31.     y=b;
  32. }
  33. dianysma::dianysma(const dianysma &allo){
  34.     x=allo.x;
  35.     y=allo.y;
  36.     arx_id=allo.arx_id;
  37. }
  38. dianysma &dianysma::operator=(const dianysma &allo){
  39.   x=allo.x;
  40.   y=allo.y;
  41.   arx_id=allo.arx_id;
  42.   return *this;
  43. }
  44. dianysma dianysma::operator+(dianysma allo){
  45.     return dianysma(x+allo.x,y+allo.y);
  46. }
  47. dianysma dianysma::operator-(dianysma allo){
  48.     return dianysma(x-allo.x,y-allo.y);
  49. }
  50. int dianysma::operator^(dianysma allo){
  51.     return (x*allo.y)-(y*allo.x);
  52. }
  53.  
  54. int N;
  55.  
  56. FILE *fin,*fout;
  57. int buff_index=0;
  58. char buff[MPOUFOS];
  59.  
  60. dianysma arx_shmeia[80005];
  61. int stoiba[40005];
  62. int tel_shmeia[80005];
  63.  
  64. int panw[40001];
  65. int panw_id[40001];
  66. int katw[40001];
  67. int katw_id[40001];
  68. bitset<40001>eida;
  69.  
  70. int comp2(const void *x,const void *y){
  71.     int ax=*((int *)x);
  72.     int bx=*((int *)y);
  73.     return ax-bx;
  74. }
  75.  
  76. inline void get_block(){
  77.     fread(buff,1,MPOUFOS,fin);
  78.     buff_index=0;
  79. }
  80.  
  81. inline char get_char(){
  82.    
  83.     char ch=buff[buff_index];
  84.    
  85.     //printf("char %c,ind %d\n",ch,buff_index);
  86.     buff_index++;
  87.     /*
  88.     if(buff_index==MPOUFOS){
  89.         get_block();
  90.     }
  91.     */
  92.     return ch;
  93. }
  94.  
  95. inline int get_int(){
  96.     int i=0;
  97.     char ch=get_char();
  98.     while(ch<'0'){
  99.         ch=get_char();
  100.     }
  101.     while(ch>='0'){
  102.         i*=10;
  103.         i+=(ch-'0');
  104.         ch=get_char();
  105.     }
  106.     return i;
  107. }
  108.  
  109. inline int ABxAC(dianysma A,dianysma B, dianysma C){
  110.     return (B-A)^(C-A);
  111. }
  112.  
  113. int main(){
  114.    
  115.     int i,j,k;
  116.    
  117.     //fin=fopen("pulsars.in","r");
  118.     fin=fopen("pulsars.big.txt","rb");
  119.     assert(fin);
  120.     get_block();
  121.    
  122.     //fscanf(fin,"%d",&N);
  123.     N=get_int();
  124.     //printf("%d\n",N);
  125.     for(i=0;i<N;i++){
  126.        
  127.         j=get_int();
  128.         k=get_int();
  129.         if(eida[j]){
  130.             if(k>panw[j]){
  131.                 panw[j]=k;
  132.                 panw_id[j]=i;
  133.             }
  134.             if(k<katw[j]){
  135.                 katw[j]=k;
  136.                 katw_id[j]=i;
  137.             }
  138.         }
  139.         else{
  140.             katw[j]=panw[j]=k;
  141.             katw_id[j]=panw_id[j]=i;
  142.         }
  143.        
  144.         eida[j]=true;
  145.        
  146.     }
  147.     /*
  148.     for(i=0;i<N;i++){
  149.         printf("%d: %d %d\n",i,arx_shmeia[i].x,arx_shmeia[i].y);
  150.     }
  151.     printf("\n");
  152.     */
  153.     fclose(fin);
  154.     //printf("party.\n");
  155.    
  156.     int real_n=0;
  157.     for(i=0;i<=40001;i++){
  158.         if(!eida[i])continue;
  159.         if(katw[i]==panw[i]){
  160.             arx_shmeia[real_n].x=i;
  161.             arx_shmeia[real_n].y=panw[i];
  162.             arx_shmeia[real_n].arx_id=panw_id[i];
  163.             real_n++;
  164.         }
  165.         else{          
  166.             arx_shmeia[real_n].x=i;
  167.             arx_shmeia[real_n].y=katw[i];
  168.             arx_shmeia[real_n].arx_id=katw_id[i];
  169.             real_n++;
  170.             arx_shmeia[real_n].x=i;
  171.             arx_shmeia[real_n].y=panw[i];
  172.             arx_shmeia[real_n].arx_id=panw_id[i];
  173.             real_n++;
  174.         }
  175.     }
  176.    
  177.     N=real_n;
  178.     /*
  179.     for(i=0;i<N;i++){
  180.         printf("%d: %d %d %d\n",i,arx_shmeia[i].x,arx_shmeia[i].y,arx_shmeia[i].arx_id);
  181.     }
  182.     */
  183.    
  184.     int top;
  185.     int ola_shmeia=0;
  186.    
  187.     //panw
  188.     stoiba[0]=0;
  189.     stoiba[1]=1;
  190.     top=1;
  191.     for(i=2;i<N;i++){
  192.        
  193.         //printf("%d %d\n",i,top);
  194.        
  195.         int e3wtiko=ABxAC(
  196.             arx_shmeia[stoiba[top-1]],
  197.             arx_shmeia[stoiba[top]],
  198.             arx_shmeia[i]
  199.         );
  200.        
  201.         if(e3wtiko<0){
  202.             //printf("<0. %d\n",i);
  203.             top++;
  204.             stoiba[top]=i;
  205.         }
  206.         else if(e3wtiko==0){
  207.             //printf("0. %d\n",i);
  208.             stoiba[top]=i;
  209.         }
  210.         else{
  211.             //printf("waa. %d\n",i);
  212.             top--;
  213.             while(
  214.                 top>0
  215.                 &&
  216.                 ABxAC(
  217.                     arx_shmeia[stoiba[top-1]],
  218.                     arx_shmeia[stoiba[top]],
  219.                     arx_shmeia[i]
  220.                 )
  221.                 >=0
  222.             ){
  223.                 //printf("\t%d\n",top);
  224.                 top--;
  225.             }
  226.             top++;
  227.             stoiba[top]=i;
  228.         }
  229.    
  230.     }
  231.     //printf("\n");
  232.     for(i=0;i<=top;i++){
  233.         //printf("%d %d %d\n",i,stoiba[i],arx_shmeia[stoiba[i]].arx_id+1);
  234.         tel_shmeia[ola_shmeia]=arx_shmeia[stoiba[i]].arx_id+1;
  235.         ola_shmeia++;
  236.     }
  237.     //katw
  238.     stoiba[0]=1;
  239.     stoiba[1]=0;
  240.     top=1;
  241.     for(i=2;i<N;i++){
  242.        
  243.         //printf("%d %d\n",i,top);
  244.        
  245.         int e3wtiko=ABxAC(
  246.             arx_shmeia[stoiba[top-1]],
  247.             arx_shmeia[stoiba[top]],
  248.             arx_shmeia[i]
  249.         );
  250.        
  251.         if(e3wtiko>0){
  252.             //printf(">0. %d\n",i);
  253.             top++;
  254.             stoiba[top]=i;
  255.         }
  256.         else if(e3wtiko==0){
  257.             //printf("0. %d\n",i);
  258.             stoiba[top]=i;
  259.         }
  260.         else{
  261.             //printf("waa. %d\n",i);
  262.             top--;
  263.             while(
  264.                 top>0
  265.                 &&
  266.                 ABxAC(
  267.                     arx_shmeia[stoiba[top-1]],
  268.                     arx_shmeia[stoiba[top]],
  269.                     arx_shmeia[i]
  270.                 )
  271.                 <=0
  272.             ){
  273.                 //printf("\t%d\n",top);
  274.                 top--;
  275.             }
  276.             top++;
  277.             stoiba[top]=i;
  278.         }
  279.    
  280.     }
  281.     //printf("\n");
  282.     for(i=0;i<=top;i++){
  283.         //printf("%d %d %d\n",i,stoiba[i],arx_shmeia[stoiba[i]].arx_id+1);
  284.         tel_shmeia[ola_shmeia]=arx_shmeia[stoiba[i]].arx_id+1;
  285.         ola_shmeia++;
  286.     }
  287.    
  288.     qsort(tel_shmeia,ola_shmeia,sizeof(int),comp2);
  289.    
  290.     //printf("\n");
  291.     i=0;
  292.     top=0;
  293.     while(i<ola_shmeia){
  294.         //printf("%d\n",tel_shmeia[i]);
  295.         j=tel_shmeia[i];
  296.         stoiba[top]=j;
  297.         top++;
  298.         while(tel_shmeia[i]==j)i++;
  299.     }
  300.     //printf("\n");
  301.     fout=fopen("pulsars.out","w");
  302.     //printf("%d\n",top);
  303.     fprintf(fout,"%d\n",top);
  304.     for(i=0;i<top;i++){
  305.         //printf("%d\n",stoiba[i]);
  306.         fprintf(fout,"%d\n",stoiba[i]);
  307.     }
  308.     fclose(fout);
  309.    
  310.     return 0;
  311. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement