Pie

[reenew]

https://www.spoj.pl/problems/PIE/

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main(){
	double ans,d,f;
	double pi = M_PI;
	vector<int> v;
	vector<int> part;
	int i,j,k,t,z;
	int T;
	int n,ff,r;
	cin>>T;
	while(T--){
		v.clear();
		part.clear();
		cin>>n>>ff;
		ff++;
		for(i=0;i<n;i++){
			cin>>r;
			r=r*r;
			v.push_back(r);
			part.push_back(2);
		}
		sort(v.rbegin(),v.rend());
		if(v.size()>=ff){
			ans = pi*v[ff-1];
			printf("%0.4f\n" ,ans);
		}
		else{
			t = v.size();
			while(t<ff){
				part[0]++;
				k = part[0];
				z = v[0];
				v.erase(v.begin());
				part.erase(part.begin());
				j=0;
				for(i=0;i<v.size();i++){
					if((z*part[i])>=(k*v[i])){
						j=1;
						v.insert(v.begin()+i,z);
						part.insert(part.begin()+i,k);
						break;
					}
				}
				if(j==0){
					v.push_back(z);
					part.push_back(k);
				}
				t++;
			}
			ans = (double)v[0]/(double)(part[0]-1);
			for(i=1;i<v.size();i++){
				d = (double)v[i]/(double)(part[i]-1);
				if(d<ans)
					ans =d;
			}
			ans = ans * pi;
			printf("%0.4f\n" ,ans);
		}
	}
	return 0;
}

I m getting wrong answer
I have tried for many test cases but still i m unable to find that case where i m wrong

please anyone provide me that case where i m wrong
thanks

[drewsalt]

the error I get is "sort was not declared in this scope"

[bbi5291]

Different installations of g++ are set up in different ways. sort() is declared in the header - the header probably includes it on SPOJ's installation and not on yours. On my installation, I can only use memset() if I have #include ; that file doesn't seem to be included elsewhere.

[reenew]

I have included algorithm library...
But still i hv got wrong answer

Please tell me whether i have logically incorrect or it's a precision mistake (in case of double)
please provide me the test cases where i m wrong

[drewsalt]

I don't think it's a precision error. You've used doubles and M_PI, that's as precise as it's going to get.

[reenew]

Hey drewsalt thnx

But i am still confused ...
I have sorted after each cut

and here i m sorting equal partitioned piece of different pies

pie[i] cut into part[i] equal pieces ,, pie[i+1] cut into part[i+1] equal pieces

thnx in advance

[bbi5291]

Your reasoning is flawed. Consider:

      if(v.size()>=ff){
         ans = pi*v[ff-1];
         printf("%0.4f\n" ,ans);
      }

So in other words, if there are at least enough pies to go around, you can give everybody a piece with size equal to that of the smallest pie, right?
Well this isn't going to work. What about a case like this:

1
2 1
1 100

There is one friend, so two people in total. There are two pies, one really big (r = 100) and one really small (r = 1).
Your output:

3.1416

That is, each person gets a piece equal in area to the smaller pie.
Correct output:

15707.963

The optimal solution is for you and your friend to split the large pie, leaving the small one untouched.

Here's a hint on how to solve this problem: Let's say each person is to get a piece of size X, can you determine whether or not this is possible?

[manish_malik]

I am getting WA for this problem spoj.pl/problems/PIE/
Here's my code

[color=#804080][bbone=text,39]Code removed[/bbone][/color]

It's giving the correct output for the given test cases. So, can somebody please give me some test cases where this goes wrong?
Also, I think there must be a better way to approach these type of problems rather than this crude method where I just took all the possibilities in consideration and coded according to that. So, if somebody can give some hint of a better algo, he's most welcome. Thanks in advance.

[gooey_kablooie_sof]

You can use binary search to solve this problem. Lets say you think everyone can get a piece of volume V. Try to find out if it is achievable. If not then all volumes above V is unachievable. You can use the absolute error of 10^(-3) to your advantage while performing the binary search.

[manish_malik]

Ok. Got it. Thanks man. Will try doing this again using binary search.

[anujthechamp]

[quote="Brian"]

15707.963

[/quote]

Please correct this, this should be 15707.9633

[nishanth_v]

continuously getting WA.Please tell me what's wrong with the code or atleast tell me a test casefor which it fails.

#include <iostream>
#include <cstdio>
#include <math.h>
#define LLI long long int
#define gc getchar_unlocked
#define pc putchar_unlocked
using namespace std;
LLI scanint()
{
register int c = gc();
LLI x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
return x;
}
LLI N,K,A[10010];
bool F(LLI x){
	LLI piece=0;
	for(LLI i=0;i<N;i++){
		piece += (A[i]/x);
		if(piece>=K)return true;
	}
	return false;
}
double BinarySearch(double lo,double hi){
	LLI mid;
	while (lo<hi){
		mid  = (LLI)(lo + (hi-lo)/2);
		if(F(mid)==true) lo = mid+1;
		else hi = mid;
	}
	return lo-1;
}
int main(){
int T;LLI x;double V;
cin>>T;
while(T--){
    N = scanint();	K = scanint();
    K++;
    for(LLI i=0;i<N;i++){
    	x = scanint();A[i] = x*x;
    }
    V = BinarySearch(1,1000000100) * M_PI ;
    printf("%.4lf\n",V);
}
return 0;
}

[mittalrishu]

can any tell me what’s wrong with this code.

#include <bits/stdc++.h>
using namespace std;

const double pi = M_PI;
const double eps = 1e-5;

bool canpiece(vector<int>& rad, double r, double f){
for(int i = 0; i < rad.size(); i++){
	double area = rad[i]*rad[i];
	double temp = r*r;
	while(area >= temp){
		area -= temp;
		f--;
	}
	if(f <= 0) return true;
  }
 return false;
}

int main(){
int t;
cin >> t;
while(t--){
	int n, f;
	cin >> n >> f;
	f++;
	vector<int> rad(n);
	for(int i = 0; i < n; i++){
		cin >> rad[i];
	}
	sort(rad.begin(), rad.end());
	
	double l = 0, h = rad[n-1];

	while(h - l > eps){
		double m = (l+h)/2;
		if(canpiece(rad, m, f)) l = m;
		else h = m - eps;
	}
	cout << fixed << setprecision(3)<< pi*h*h<< endl;
}

}