infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Totul pare OK!
Pagini: [1]   În jos
« mesajul precedent următorul mesaj »
  Imprimă  
Ajutor Subiect: Totul pare OK!  (Citit de 2820 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•chera_lary
De-al casei
***

Karma: -2
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« : Noiembrie 14, 2009, 20:29:31 »
Salut!
De ce obtin numai 75 de puncte pe problema aceasta : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=971?
Cod:
#include <cstdio>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
const int maxn = 120000;
const int INF = 1000000001;
 
double X[maxn],Y[maxn];
//long double V[maxn];
int PI,IND[maxn],N,ST[maxn];
 
bool cmpf(int i,int j)
{
	return (double)(X[i] - X[PI]) * (Y[j] - Y[PI]) < (double)(X[j] - X[PI]) * (Y[i] - Y[PI]);
}
 
long double semn(int i1,int i2,int i3)
{
	return (long double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}
 
int main()
{
	freopen("cetati.in","r",stdin);
	freopen("cetati.out","w",stdout);
	scanf("%d\n",&N);
	X[0] = INF;Y[0] = INF;
	int punct_initial = 0;
	for(int i = 1;i <= N; ++i)
	{
		scanf("%lf %lf",&X[i],&Y[i]);
		if (X[i] < X[punct_initial] || (X[i] == X[punct_initial] && Y[i] < Y[punct_initial])) punct_initial = i;
	}
	PI = punct_initial;
	for(int i = 1;i <= N; ++i)
	{
		if (i == punct_initial) continue;
		IND[++IND[0]] = i;
	}
	sort(IND + 1,IND + IND[0] + 1,cmpf);
	ST[ST[0] = 1] = punct_initial;
	for(int i = 1;i <= IND[0]; ++i)
	{
		if (IND[i] == punct_initial) continue;
		while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) > 0) --ST[0];
		ST[++ST[0]] = IND[i];
	}
	ST[++ST[0]] = punct_initial;
	printf("%d\n",N - (int)(ST[0]-1));
	/*reverse(ST + 1, ST + ST[0] + 1);
	for(int i = 1;i < ST[0]; ++i)
	{
		printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);
	}*/
	return 0;
}
« Ultima modificare: Noiembrie 14, 2009, 21:09:21 de către CHERA Laurentiu » Memorat
•APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #1 : Noiembrie 14, 2009, 21:07:56 »
Citat din mesajul lui: CHERA Laurentiu din Noiembrie 14, 2009, 20:29:31
Salut!
De ce obint numai 75 de puncte pe problema aceasta : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=971?
Cod:
#include <cstdio>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
const int maxn = 120000;
const int INF = 1000000001;
 
double X[maxn],Y[maxn];
//long double V[maxn];
int PI,IND[maxn],N,ST[maxn];
 
bool cmpf(int i,int j)
{
	return (double)(X[i] - X[PI]) * (Y[j] - Y[PI]) < (double)(X[j] - X[PI]) * (Y[i] - Y[PI]);
}
 
long double semn(int i1,int i2,int i3)
{
	return (long double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}
 
int main()
{
	freopen("cetati.in","r",stdin);
	freopen("cetati.out","w",stdout);
	scanf("%d\n",&N);
	X[0] = INF;Y[0] = INF;
	int punct_initial = 0;
	for(int i = 1;i <= N; ++i)
	{
		scanf("%lf %lf",&X[i],&Y[i]);
		if (X[i] < X[punct_initial] || (X[i] == X[punct_initial] && Y[i] < Y[punct_initial])) punct_initial = i;
	}
	PI = punct_initial;
	for(int i = 1;i <= N; ++i)
	{
		if (i == punct_initial) continue;
		IND[++IND[0]] = i;
	}
	sort(IND + 1,IND + IND[0] + 1,cmpf);
	ST[ST[0] = 1] = punct_initial;
	for(int i = 1;i <= IND[0]; ++i)
	{
		if (IND[i] == punct_initial) continue;
		while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) > 0) --ST[0];
		ST[++ST[0]] = IND[i];
	}
	ST[++ST[0]] = punct_initial;
	printf("%d\n",N - (int)(ST[0]-1));
	/*reverse(ST + 1, ST + ST[0] + 1);
	for(int i = 1;i < ST[0]; ++i)
	{
		printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);
	}*/
	return 0;
}
io am bagat shi pe infoarena shi pe campion aproximativ acelashi cod doar output-ul schimbat shi pe infoarena iau 100 pe campion 60
Memorat
•alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #2 : Noiembrie 14, 2009, 22:21:54 »
ia primul test care nu-ti merge si fa un debug, poate iti dai seamna Wink.
Memorat
•chera_lary
De-al casei
***

Karma: -2
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #3 : Noiembrie 14, 2009, 23:16:39 »
Da, am incercat, da un raspuns gresit, insa nu imi dau seama care ar fi hiba(legat de primul test, voua va merge tot timpul sa download-ati testele acelea si raspunsurile oficiale?).
Memorat
•yonatan
Strain
*

Karma: 10
Deconectat Deconectat

Mesaje: 47



Vezi Profilul
« Răspunde #4 : Noiembrie 14, 2009, 23:23:22 »
Citat din mesajul lui: CHERA Laurentiu din Noiembrie 14, 2009, 23:16:39
Da, am incercat, da un raspuns gresit, insa nu imi dau seama care ar fi hiba(legat de primul test, voua va merge tot timpul sa download-ati testele acelea si raspunsurile oficiale?).
e foarte simplu fratilor trebuie luat shi cazul de coliniaritate in seama io am luat 100. SKIMBA-N ASTA:
Cod:
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<iomanip>
using namespace std;
struct data{
    double x;
    double y;
    long mark;
    long ind;
    long index;
};
data pct[120000],aux;
long n;

bool compare(data i,data j)
{return ((i.x-pct[1].x)*(j.y-pct[1].y)<(i.y-pct[1].y)*(j.x-pct[1].x));
}
int main()
{vector<int> stiva;
int k,i,u,w;
long min=1;



ifstream fin("cetati.in");

    fin>>n;
    for(i=1;i<=n;i++)
      {fin>>pct[i].x>>pct[i].y;
      pct[i].ind=i;
}

fin.close();
    for(i=2;i<=n;i++)
       {if(pct[i].x<pct[min].x)
       min=i;}

    aux=pct[min];
    pct[min]=pct[1];
    pct[1]=aux;
    sort(pct+2,pct+n+1,compare);
    for(i=1;i<=n;i++)
      pct[i].index=i;
    stiva.push_back(0);
    stiva.push_back(pct[1].index);
    stiva.push_back(pct[2].index);
    stiva.push_back(pct[3].index);

    k=3;
    u=stiva[k-1];
    w=stiva[k];
    for(i=4;i<=n;i++)
        {while(k>2&&((pct[w].x - pct[u].x)*(pct[i].y - pct[u].y)-(pct[w].y - pct[u].y)*(pct[i].x - pct[u].x)>=0))
        //(pct[u].x * pct[w].y + pct[w].x * pct[i].y + pct[i].x * pct[u].y - pct[u].y * pct[w].x - pct[w].y * pct[i].x - pct[i].y * pct[u].x)>0)
        //(pct[k].x - pct[k-1].x)*(pct[i].y - pct[k-1].y)<(pct[k].y - pct[k-1].y)*(pct[i].x - pct[k-1].x))
           {k=k-1;
            u=stiva[k-1];
            w=stiva[k];
            stiva.pop_back();

           }

         k=k+1;
         u=stiva.back();
         w=pct[i].index;
         stiva.push_back(pct[i].index);
        }

  ofstream fout("cetati.out");
  fout<<n-k<<'\n';

  fout.close();


    return 0;
}

si trebuie sa mearga. daca eshti atent la while-ul meu o sa intzelegi unde era buba Ok
Memorat
•chera_lary
De-al casei
***

Karma: -2
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #5 : Noiembrie 14, 2009, 23:32:48 »
Multumesc! Very Happy Ok
Memorat
•Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #6 : Noiembrie 14, 2009, 23:34:36 »
Ce se cere pe .campion, nu e chiar ce se găsește în arhiva educațională, unde una din condiții este ca punctele de pe infasurătoare să nu fie coliniare (adevărul este că și enunțul problemei este foarte vag și nu specifică nimic). Așa că trebuie să vezi cum faci când stabilești unghiul acela (mai bine zis semnul determinantului Smile ).
Memorat
•chera_lary
De-al casei
***

Karma: -2
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #7 : Noiembrie 14, 2009, 23:41:12 »
Da, problema are un enunt destul de confuz! Merge mai repede algoritmul acesta:
Cod:
#include <cstdio>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
const int maxn = 120000;
const int INF = 1000000001;
 
double X[maxn],Y[maxn];
//long double V[maxn];
int PI,IND[maxn],N,ST[maxn];
 
bool cmpf(int i,int j)
{
	return (double)(X[i] - X[PI]) * (Y[j] - Y[PI]) < (double)(X[j] - X[PI]) * (Y[i] - Y[PI]);
}
 
long double semn(int i1,int i2,int i3)
{
	return (long double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}
 
int main()
{
	freopen("cetati.in","r",stdin);
	freopen("cetati.out","w",stdout);
	scanf("%d\n",&N);
	X[0] = INF;Y[0] = INF;
	int punct_initial = 0;
	for(int i = 1;i <= N; ++i)
	{
		scanf("%lf %lf",&X[i],&Y[i]);
		if (X[i] < X[punct_initial] || (X[i] == X[punct_initial] && Y[i] < Y[punct_initial])) punct_initial = i;
	}
	PI = punct_initial;
	for(int i = 1;i <= N; ++i)
	{
		if (i == punct_initial) continue;
		IND[++IND[0]] = i;
	}
	sort(IND + 1,IND + IND[0] + 1,cmpf);
	ST[ST[0] = 1] = punct_initial;
	for(int i = 1;i <= IND[0]; ++i)
	{
		if (IND[i] == punct_initial) continue;
		while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) >= 0) --ST[0];
		ST[++ST[0]] = IND[i];
	}
	ST[++ST[0]] = punct_initial;
	printf("%d\n",N - (int)(ST[0]-1));
	/*reverse(ST + 1, ST + ST[0] + 1);
	for(int i = 1;i < ST[0]; ++i)
	{
		printf("%lf %lf\n",X[ST[i]],Y[ST[i]]);
	}*/
	return 0;
}
« Ultima modificare: Noiembrie 14, 2009, 23:47:46 de către CHERA Laurentiu » Memorat
•miculprogramator
Nu mai tace
*****

Karma: 65
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #8 : Noiembrie 15, 2009, 09:14:18 »
@Laurentiu: legat de testele acelea, nu le poti lua din cauza browserului. Cel putin la mine asa era cand foloseam Mozilla. Pe IE si Flock mergea. Am pus Chrome si e perfect. Smile
Memorat
•alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #9 : Noiembrie 15, 2009, 09:18:44 »
Citat din mesajul lui: ALbulescu Cosmina din Noiembrie 15, 2009, 09:14:18
@Laurentiu: legat de testele acelea, nu le poti lua din cauza browserului. Cel putin la mine asa era cand foloseam Mozilla. Pe IE si Flock mergea. Am pus Chrome si e perfect. Smile
Merge si pe Mozilla Tongue
Memorat
Pagini: [1]   În sus
  Imprimă  
infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Totul pare OK!
 « mesajul precedent următorul mesaj »
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines