10034 - Freckles
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
Try Kruskal's algorithm.
Check input and AC output for thousands of problems on uDebug!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
What if there are >= 100 test cases?
Don't print a blank line at the start of the output.
It doesn't matter the order, so it is easier to print the output right away.
Try to separate the input from the output when you're running the code. You can redirect them to and from files for testing, but the code you submit should read from stdin and write to stdout.
Don't print a blank line at the start of the output.
It doesn't matter the order, so it is easier to print the output right away.
Try to separate the input from the output when you're running the code. You can redirect them to and from files for testing, but the code you submit should read from stdin and write to stdout.
Check input and AC output for thousands of problems on uDebug!
Re: 10034 - Freckles
Code: Select all
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define x first
#define y second
#define MAX 110
typedef pair<double,double>pii;
pii point[MAX];
int parent[MAX];
struct edge
{
int a,b;
double w;
bool operator<(const edge &ob) const
{
return(w<ob.w);
}
}ee;
vector<edge> graph;
int find_ref(int r)
{
if(parent[r]==r)
return r;
else
return parent[r]=find_ref(parent[r]);
}
double calC(pii a,pii b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double mst(int n)
{
int count=0;
double sum=0.0;
sort(graph.begin(),graph.end());
for(int i=0;i<graph.size();i++)
{
int u_ref=find_ref(graph[i].a);
int v_ref=find_ref(graph[i].b);
if(u_ref!=v_ref)
{
parent[graph[i].a]=graph[i].b;
sum+=graph[i].w;
count++;
if(count==n-1)
break;
}
}
return sum;
}
int main(void)
{
//freopen("FILE.txt","w",stdout);
int testcase;
cin>>testcase;
while(testcase--)
{
graph.clear();
memset(parent,0,sizeof(parent));
memset(&ee,0,sizeof(edge));
memset(point,0,sizeof(point));
int n;
cin>>n; //number of freckles
for(int i=0;i<n;i++)
{ cin>>point[i].x>>point[i].y; //taking points as input and
parent[i]=i; //creating the set
}
for(int i=0;i<n-1;i++) //creating the complete graph here
{
for(int j=i+1;j<n;j++)
{
ee.a=i;
ee.b=j;
ee.w=calC(point[i],point[j]);
graph.push_back(ee);
//cout<<ee.a.x<<" "<<ee.a.y<<" "<<ee.b.x<<" "<<ee.b.y<<" "<<ee.w<<endl;
}
}
printf("%0.2lf\n",mst(n));
if(testcase!=0)
printf("\n");
}
return 0;
}
-
- New poster
- Posts: 1
- Joined: Fri Dec 27, 2013 2:42 pm
Re: 10034 - Freckles
Could anybody with AC give me her/his outs for this data?
Thx in advance!
Thx in advance!
Code: Select all
100
7
4 0
1 0
3 9
1 9
2 8
5 5
1 5
7
4 2
6 4
2 1
8 4
3 5
6 0
0 0
7
4 4
3 1
2 8
0 8
1 8
5 5
5 0
7
2 6
9 5
3 4
5 5
8 1
9 5
2 8
7
2 4
2 8
1 5
3 7
1 8
2 9
5 4
7
5 5
6 8
3 7
7 7
9 9
6 0
7 6
7
1 0
3 9
7 9
7 2
5 2
8 5
8 3
7
8 9
5 6
3 0
0 7
3 2
3 7
8 7
7
6 1
6 2
8 9
6 0
5 4
8 6
4 8
7
3 1
0 1
7 9
7 8
9 9
1 5
0 4
7
0 6
0 2
0 2
9 5
4 8
6 2
5 8
7
8 1
8 7
1 7
0 1
0 3
5 3
2 2
7
8 1
5 7
3 5
0 3
3 3
7 9
5 2
7
2 7
0 0
2 4
5 4
7 8
3 8
2 8
7
5 4
0 5
8 8
5 7
0 0
4 5
5 6
7
5 5
0 4
5 9
8 2
2 0
8 3
4 1
7
5 2
4 7
4 7
0 3
1 1
1 7
4 9
7
5 8
9 3
5 6
7 3
2 9
4 6
3 3
7
9 7
3 0
7 4
9 9
6 1
8 4
7 2
7
0 3
9 5
0 0
2 1
5 9
5 9
6 9
7
5 3
3 7
5 9
4 9
7 5
3 8
9 0
7
9 8
4 7
6 1
1 9
6 7
4 3
8 6
7
9 6
0 7
6 2
8 2
9 9
8 7
8 7
7
9 6
9 5
0 7
2 7
6 4
4 2
0 1
7
4 8
1 1
1 0
4 0
2 6
3 8
1 2
7
0 0
4 6
3 5
6 9
2 2
0 3
2 2
7
2 1
0 7
4 2
0 1
7 9
9 8
7 1
7
9 5
3 5
3 0
0 3
5 3
0 6
8 6
7
4 8
9 9
1 8
7 8
6 3
5 1
1 7
7
6 2
0 6
2 9
0 2
2 0
1 9
9 0
7
7 7
9 9
5 2
1 4
7 9
9 0
6 2
7
9 5
7 8
2 0
5 2
2 4
9 0
0 4
7
7 1
1 8
7 0
8 5
5 6
5 8
6 1
7
3 7
3 4
2 9
2 6
4 2
4 5
4 2
7
4 0
6 0
5 4
6 8
0 0
3 4
3 2
7
6 7
2 7
9 4
9 4
1 1
8 7
1 7
7
7 1
2 8
8 2
1 5
9 8
9 7
1 6
7
3 3
5 7
3 1
6 0
0 7
9 0
5 7
7
7 0
6 9
6 9
9 1
1 3
0 1
1 7
7
7 3
0 5
7 2
9 8
3 3
6 4
3 2
7
1 8
5 2
5 4
8 4
3 4
4 6
1 7
7
5 0
6 0
0 4
5 9
8 5
8 9
4 9
7
4 1
3 2
0 0
0 5
6 4
6 7
8 1
7
0 3
8 1
5 7
8 0
3 3
2 4
7 5
7
4 3
3 7
0 3
9 1
6 7
2 2
2 6
7
8 0
3 7
8 2
4 4
5 5
5 3
9 4
7
9 7
5 9
6 8
6 9
6 2
9 7
9 3
7
0 1
9 0
1 1
3 6
1 2
3 4
8 0
7
7 4
1 9
8 1
9 9
7 5
9 0
1 0
7
0 3
4 8
0 0
9 5
2 5
2 0
2 0
7
9 8
7 6
6 8
6 9
1 9
0 1
7 5
7
3 4
2 4
5 0
2 4
5 8
6 2
6 5
7
6 6
9 9
1 0
9 7
9 3
3 0
9 5
7
3 0
5 6
5 5
5 1
1 7
1 4
7 3
7
0 4
4 1
5 3
1 5
5 5
9 0
6 8
7
5 6
8 2
8 2
6 7
5 0
3 4
8 7
7
6 8
3 5
2 3
5 7
9 7
0 0
2 0
7
3 9
8 3
0 0
4 9
4 1
1 7
3 2
7
0 3
4 3
7 8
0 1
6 3
6 8
6 9
7
8 8
3 5
8 2
3 3
9 6
7 0
2 3
7
5 0
2 9
6 9
7 2
2 4
8 2
0 0
7
3 6
4 9
2 5
0 3
3 2
0 1
9 1
7
3 5
9 5
2 7
0 7
9 8
9 1
5 7
7
2 0
6 2
3 7
4 0
5 5
1 1
5 1
7
9 9
7 7
6 7
4 6
5 3
4 9
7 6
7
7 1
6 0
2 1
8 3
8 3
4 3
2 8
7
6 7
3 0
0 8
2 2
8 3
3 8
8 4
7
2 7
6 5
5 2
5 7
1 8
5 4
4 9
7
2 6
0 4
7 4
2 8
0 1
7 9
3 4
7
1 5
5 5
2 3
4 6
8 6
4 7
9 3
7
2 8
2 2
3 8
9 1
3 5
7 6
9 0
7
7 6
7 6
4 7
7 2
9 0
2 7
3 7
7
3 3
3 4
1 8
7 5
5 0
8 8
4 6
7
9 8
6 1
8 9
7 1
5 7
3 0
6 0
7
0 4
5 0
0 7
2 5
5 6
5 5
4 9
7
4 8
2 0
5 1
7 0
9 5
3 7
8 2
7
0 0
9 3
1 2
1 4
0 0
5 7
6 9
7
8 5
0 1
0 2
1 8
7 8
3 1
2 9
7
3 7
2 0
3 8
0 8
4 2
4 3
1 6
7
5 1
4 3
5 6
2 0
1 8
5 8
4 5
7
4 6
2 1
1 5
2 1
6 9
0 5
8 2
7
9 5
9 4
1 1
3 5
6 9
0 5
2 6
7
4 4
9 2
4 3
3 7
3 9
3 3
3 7
7
1 7
6 5
5 4
0 7
4 9
7 2
6 7
7
4 5
0 1
4 1
9 6
3 0
0 5
7 9
7
0 6
3 5
0 0
6 8
7 9
2 3
0 9
7
2 8
0 0
3 8
0 9
7 4
1 1
3 9
7
6 3
7 2
7 9
2 6
0 8
9 1
3 6
7
0 3
0 2
5 8
5 2
9 7
3 2
1 5
7
9 3
5 8
1 0
0 0
3 1
2 4
8 6
7
4 1
4 5
9 2
7 3
6 8
6 6
6 5
7
7 5
5 9
1 5
1 3
8 3
2 5
4 6
7
3 0
9 0
3 8
7 1
9 6
0 6
4 1
7
4 4
6 4
5 5
9 7
0 4
0 2
5 4
7
7 9
6 2
9 3
1 4
3 9
3 5
5 5
7
0 5
4 0
4 2
9 7
6 8
2 4
4 6
7
6 4
5 1
9 5
0 2
4 9
9 3
6 7
7
3 3
1 2
4 6
8 9
4 9
2 5
3 8
7
1 6
2 9
8 2
2 4
0 2
5 6
8 5
7
7 7
8 4
9 7
5 2
1 3
0 1
9 3
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
Check input and AC output for thousands of problems on uDebug!
Re: 10034 - Freckles
I.I got WA no idea why, I really have tried every test case in this forum and all output is correct
Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[100];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cout<<"\n";
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i]<<"\n";
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
Don't print a blank line at the start of the output
Check input and AC output for thousands of problems on uDebug!
Re: 10034 - Freckles
Sorry for late reply . Tried . But still showing wa.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
Post your updated code.
Check input and AC output for thousands of problems on uDebug!
Re: 10034 - Freckles
Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[10000];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i]<<"\n";
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
The outputs of two consecutive cases will be separated by a blank line.
Check input and AC output for thousands of problems on uDebug!
Re: 10034 - Freckles
Did . Bt still wa .
Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[10000];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i];
cout<<"\n";
cout<<"\n";
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
Don't print an extra blank line at the end of the output.
Check input and AC output for thousands of problems on uDebug!
Re: 10034 - Freckles
Still WA."For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. " Dont I need to print the extra blank line ?? I tried omitting both newline one by one . In both cases I got WA.
Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[10000];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i];
cout<<"\n";
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10034 - Freckles
The outputs of two consecutive cases will be separated by a blank line.
For input:AC output:
For input:
Code: Select all
2
3
1.0 1.0
2.0 2.0
2.0 4.0
3
1.0 1.0
2.0 2.0
2.0 4.0
Code: Select all
3.41
3.41
Check input and AC output for thousands of problems on uDebug!