Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdio.h"
- #include "assert.h"
- #include "stdlib.h"
- #include <iostream>
- #include <bitset>
- using namespace std;
- #define MPOUFOS (14*1024*1024)
- class dianysma{
- public:
- int x;
- int y;
- int arx_id;
- dianysma();
- dianysma(int,int);
- dianysma(const dianysma &);
- dianysma &operator=(const dianysma &);
- dianysma operator+(dianysma);
- dianysma operator-(dianysma);
- int operator^(dianysma);
- };
- dianysma::dianysma(){
- }
- dianysma::dianysma(int a, int b){
- x=a;
- y=b;
- }
- dianysma::dianysma(const dianysma &allo){
- x=allo.x;
- y=allo.y;
- arx_id=allo.arx_id;
- }
- dianysma &dianysma::operator=(const dianysma &allo){
- x=allo.x;
- y=allo.y;
- arx_id=allo.arx_id;
- return *this;
- }
- dianysma dianysma::operator+(dianysma allo){
- return dianysma(x+allo.x,y+allo.y);
- }
- dianysma dianysma::operator-(dianysma allo){
- return dianysma(x-allo.x,y-allo.y);
- }
- int dianysma::operator^(dianysma allo){
- return (x*allo.y)-(y*allo.x);
- }
- int N;
- FILE *fin,*fout;
- int buff_index=0;
- char buff[MPOUFOS];
- dianysma arx_shmeia[80005];
- int stoiba[40005];
- int tel_shmeia[80005];
- int panw[40001];
- int panw_id[40001];
- int katw[40001];
- int katw_id[40001];
- bitset<40001>eida;
- int comp2(const void *x,const void *y){
- int ax=*((int *)x);
- int bx=*((int *)y);
- return ax-bx;
- }
- inline void get_block(){
- fread(buff,1,MPOUFOS,fin);
- buff_index=0;
- }
- inline char get_char(){
- char ch=buff[buff_index];
- //printf("char %c,ind %d\n",ch,buff_index);
- buff_index++;
- /*
- if(buff_index==MPOUFOS){
- get_block();
- }
- */
- return ch;
- }
- inline int get_int(){
- int i=0;
- char ch=get_char();
- while(ch<'0'){
- ch=get_char();
- }
- while(ch>='0'){
- i*=10;
- i+=(ch-'0');
- ch=get_char();
- }
- return i;
- }
- inline int ABxAC(dianysma A,dianysma B, dianysma C){
- return (B-A)^(C-A);
- }
- int main(){
- int i,j,k;
- //fin=fopen("pulsars.in","r");
- fin=fopen("pulsars.big.txt","rb");
- assert(fin);
- get_block();
- //fscanf(fin,"%d",&N);
- N=get_int();
- //printf("%d\n",N);
- for(i=0;i<N;i++){
- j=get_int();
- k=get_int();
- if(eida[j]){
- if(k>panw[j]){
- panw[j]=k;
- panw_id[j]=i;
- }
- if(k<katw[j]){
- katw[j]=k;
- katw_id[j]=i;
- }
- }
- else{
- katw[j]=panw[j]=k;
- katw_id[j]=panw_id[j]=i;
- }
- eida[j]=true;
- }
- /*
- for(i=0;i<N;i++){
- printf("%d: %d %d\n",i,arx_shmeia[i].x,arx_shmeia[i].y);
- }
- printf("\n");
- */
- fclose(fin);
- //printf("party.\n");
- int real_n=0;
- for(i=0;i<=40001;i++){
- if(!eida[i])continue;
- if(katw[i]==panw[i]){
- arx_shmeia[real_n].x=i;
- arx_shmeia[real_n].y=panw[i];
- arx_shmeia[real_n].arx_id=panw_id[i];
- real_n++;
- }
- else{
- arx_shmeia[real_n].x=i;
- arx_shmeia[real_n].y=katw[i];
- arx_shmeia[real_n].arx_id=katw_id[i];
- real_n++;
- arx_shmeia[real_n].x=i;
- arx_shmeia[real_n].y=panw[i];
- arx_shmeia[real_n].arx_id=panw_id[i];
- real_n++;
- }
- }
- N=real_n;
- /*
- for(i=0;i<N;i++){
- printf("%d: %d %d %d\n",i,arx_shmeia[i].x,arx_shmeia[i].y,arx_shmeia[i].arx_id);
- }
- */
- int top;
- int ola_shmeia=0;
- //panw
- stoiba[0]=0;
- stoiba[1]=1;
- top=1;
- for(i=2;i<N;i++){
- //printf("%d %d\n",i,top);
- int e3wtiko=ABxAC(
- arx_shmeia[stoiba[top-1]],
- arx_shmeia[stoiba[top]],
- arx_shmeia[i]
- );
- if(e3wtiko<0){
- //printf("<0. %d\n",i);
- top++;
- stoiba[top]=i;
- }
- else if(e3wtiko==0){
- //printf("0. %d\n",i);
- stoiba[top]=i;
- }
- else{
- //printf("waa. %d\n",i);
- top--;
- while(
- top>0
- &&
- ABxAC(
- arx_shmeia[stoiba[top-1]],
- arx_shmeia[stoiba[top]],
- arx_shmeia[i]
- )
- >=0
- ){
- //printf("\t%d\n",top);
- top--;
- }
- top++;
- stoiba[top]=i;
- }
- }
- //printf("\n");
- for(i=0;i<=top;i++){
- //printf("%d %d %d\n",i,stoiba[i],arx_shmeia[stoiba[i]].arx_id+1);
- tel_shmeia[ola_shmeia]=arx_shmeia[stoiba[i]].arx_id+1;
- ola_shmeia++;
- }
- //katw
- stoiba[0]=1;
- stoiba[1]=0;
- top=1;
- for(i=2;i<N;i++){
- //printf("%d %d\n",i,top);
- int e3wtiko=ABxAC(
- arx_shmeia[stoiba[top-1]],
- arx_shmeia[stoiba[top]],
- arx_shmeia[i]
- );
- if(e3wtiko>0){
- //printf(">0. %d\n",i);
- top++;
- stoiba[top]=i;
- }
- else if(e3wtiko==0){
- //printf("0. %d\n",i);
- stoiba[top]=i;
- }
- else{
- //printf("waa. %d\n",i);
- top--;
- while(
- top>0
- &&
- ABxAC(
- arx_shmeia[stoiba[top-1]],
- arx_shmeia[stoiba[top]],
- arx_shmeia[i]
- )
- <=0
- ){
- //printf("\t%d\n",top);
- top--;
- }
- top++;
- stoiba[top]=i;
- }
- }
- //printf("\n");
- for(i=0;i<=top;i++){
- //printf("%d %d %d\n",i,stoiba[i],arx_shmeia[stoiba[i]].arx_id+1);
- tel_shmeia[ola_shmeia]=arx_shmeia[stoiba[i]].arx_id+1;
- ola_shmeia++;
- }
- qsort(tel_shmeia,ola_shmeia,sizeof(int),comp2);
- //printf("\n");
- i=0;
- top=0;
- while(i<ola_shmeia){
- //printf("%d\n",tel_shmeia[i]);
- j=tel_shmeia[i];
- stoiba[top]=j;
- top++;
- while(tel_shmeia[i]==j)i++;
- }
- //printf("\n");
- fout=fopen("pulsars.out","w");
- //printf("%d\n",top);
- fprintf(fout,"%d\n",top);
- for(i=0;i<top;i++){
- //printf("%d\n",stoiba[i]);
- fprintf(fout,"%d\n",stoiba[i]);
- }
- fclose(fout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement