Titlul: Totul pare OK!
Scris de: CHERA Laurentiu din 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 (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=971)? #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;
}
Titlul: Răspuns: Totul pare OK!
Scris de: Dragos din Noiembrie 14, 2009, 21:07:56
Salut! De ce obint numai 75 de puncte pe problema aceasta : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=971 (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=971)? #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
Titlul: Răspuns: Totul pare OK!
Scris de: alexandru din Noiembrie 14, 2009, 22:21:54
ia primul test care nu-ti merge si fa un debug, poate iti dai seamna ;).
Titlul: Răspuns: Totul pare OK!
Scris de: 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?).
Titlul: Răspuns: Totul pare OK!
Scris de: Cont de teste din Noiembrie 14, 2009, 23:23:22
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: #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:
Titlul: Răspuns: Totul pare OK!
Scris de: CHERA Laurentiu din Noiembrie 14, 2009, 23:32:48
Multumesc! :D :ok:
Titlul: Răspuns: Totul pare OK!
Scris de: Andrei Misarca din 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 :) ).
Titlul: Răspuns: Totul pare OK!
Scris de: CHERA Laurentiu din Noiembrie 14, 2009, 23:41:12
Da, problema are un enunt destul de confuz! Merge mai repede algoritmul acesta: #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;
}
Titlul: Răspuns: Totul pare OK!
Scris de: A Cosmina - vechi 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. :)
Titlul: Răspuns: Totul pare OK!
Scris de: alexandru din Noiembrie 15, 2009, 09:18:44
@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. :)
Merge si pe Mozilla :P
|