## 10034 - Freckles

Moderator: Board moderators

brianfry713
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!

brianfry713
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.
Check input and AC output for thousands of problems on uDebug!

Skynet094
New poster
Posts: 3
Joined: Fri Jul 19, 2013 6:31 pm

### 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;
}
Help, Passes all the testcases from the forum.Still getting WA.

piotrmizerka
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?

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

brianfry713
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!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

### 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;

}

brianfry713
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!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

### Re: 10034 - Freckles

Sorry for late reply . Tried . But still showing wa.

brianfry713
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!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

### 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;

}

brianfry713
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!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

### 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;

}

brianfry713
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!

bitaron
New poster
Posts: 12
Joined: Mon Jan 06, 2014 9:40 pm

### 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;

}

brianfry713
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:

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
AC output:

Code: Select all

3.41

3.41
Check input and AC output for thousands of problems on uDebug!