527 - The partition of a cake

[medv]

Can smb tell me the idea of solving this task? (The partition of a cake)

[ali_chan]

Can smb tell me the idea of solving this task? (The partition of a cake)

Rep:
This problem was not very difficult. Let's draw the lines one after the other. First line is simple - it divides the plane into 2 parts. Let's now have n lines in the plane. They divide the plane into m parts. What happens, when we now add the (n+1)th line ? First n lines will cut r different intersections on it. These r intersections will divide our line into r+1 segments. And each of the segments will divide one part of the plane into two parts. Also r+1 new parts will arise.

So the idea of the algorithm is clear - we will process the lines one after the other. For each line, we compute its intersections with all the previous lines, sort them to find out how many different intersections are there and finally we update the current number of parts.

I copy this algorithm from ipsc website: year 2000, problem B("Cake")
http://ipsc.ksp.sk/problems/ipsc2000/sol_b.php

Regards,

ali

[SilVer DirectXer]

[cpp]
#include <stdio.h>
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
int total_l;
int world[1001][1001];
int list[1001],need=0;
int right;
class cord{
public:
int x;
int y;
};
void calc1_0(int i,int j,int k);
cord pt1[1000],pt2[1000];
void main(void)
{
int i,j,k;

while(1)
{
need=0;
cin>>total_l;

if (feof(stdin))
break;

for(i=0;i<=1000;i++)
for(j=0;j<=1000;j++)
world[j]=0;

for (i=0;i<=1000;i++)
list=-1;


for (i=0;i<total_l;i++)
{
cin>>pt1.x>>pt1.y;
cin>>pt2.x>>pt2.y;
}

for(i=0;i<=1000;i++)
for(j=0;j<=1000;j++)
for(k=0;k<total_l;k++)
{
calc1_0(i,j,k);
}

for(i=0;i<=1000;i++)
for(j=0;j<=1000;j++)
{
right=0;
for (k=0;k<=need;k++)
{
if (world[j]==list[k])
{
right=1;
break;
}
}
if (right==0)
{
list[need]=world[j];
need++;
}
}

cout<<need<<endl;
}


}

void calc1_0(int i, int j ,int k)
{
double po_ne;
int po_nel;

po_ne=(pt2[k].y-pt1[k].y)/(double)(pt2[k].x-pt1[k].x);
po_ne*=(j-pt1[k].x);
po_ne=i-pt1[k].y-po_ne;
world[j]*=2;
if (po_ne>0)
world[j]++;
}

[/cpp]

please help me to take a look.

[Tompik]

[pascal]
Why WA? There is my code, but i don't understand, why i've got WA. Please Somebody help me.
program ppp;
{$APPTYPE CONSOLE}
const max = 1000;

type
tvector = record x,y : comp; end;
trational = record c,m : comp; end;
trational_point = record x,y : trational; end;

var lines : array[1..max,1..2] of tvector;
n,i,j : integer;
f : text;
parts : integer;
ok: boolean;
intersect : array[1..max] of trational_point;

procedure read_line(ix : integer);
var b1,b2 : tvector;
j: integer;
begin
ok:=true;
read(b1.x,b1.y,b2.x,b2.y);
for j:=1 to ix-1 do
begin
if (b1.x=lines[j,1].x) and (b1.y=lines[j,1].y) then
if ((b2.x-b1.x)=lines[j,2].x) and ((b2.y-b1.y)=lines[j,2].y)
then ok:=false;
end;
lines[ix,1].x:=b1.x;
lines[ix,1].y:=b1.y;
lines[ix,2].x:=b2.x-b1.x;
lines[ix,2].y:=b2.y-b1.y;
end;

function count_intersections(p1,p2 : integer; var pr : trational_point) : boolean;
var k1,k2 : comp;
qw: integer;
begin
{are the lines parallel ?}
if lines[p1,2].x*lines[p2,2].y=lines[p1,2].y*lines[p2,2].x then begin
count_intersections:=false; exit;
end;
{count the coordinates of their intersection}
k1:=lines[p2,2].y*(lines[p2,1].x-lines[p1,1].x)-lines[p2,2].x*(lines[p2,1].y-lines[p1,1].y);
k2:=lines[p1,2].x*lines[p2,2].y-lines[p1,2].y*lines[p2,2].x;
pr.x.c:=k2*lines[p1,1].x+k1*lines[p1,2].x;
pr.x.m:=k2;
pr.y.c:=k2*lines[p1,1].y+k1*lines[p1,2].y;
pr.y.m:=k2;
if k2<0 then begin
pr.x.c:=-pr.x.c;
pr.x.m:=-pr.x.m;
pr.y.c:=-pr.y.c;
pr.y.m:=-pr.y.m;
end;
if ((pr.x.c/pr.x.m)>=1000) or ((pr.y.c/pr.y.m)>=1000) or ((pr.x.c/pr.x.m)<=0) or ((pr.y.c/pr.y.m)<=0) then begin
count_intersections:=false; exit;
end;
count_intersections:=true;
end;

function less(b1,b2 : trational_point) : boolean;
begin
{compare two rational numbers}
less:=false;
if b1.x.c*b2.x.m<b1.x.m*b2.x.c then begin less:=true; exit; end;
if (b1.x.c*b2.x.m=b1.x.m*b2.x.c)
and (b1.y.c*b2.y.m<b1.y.m*b2.y.c)
then begin less:=true; exit; end;
end;

procedure sort(l,r:integer);
var
i, j: integer;
x, y : trational_point;
begin
i:=l; j:=r; x:=intersect[(l+r) DIV 2];
repeat
while less(intersect,x) do inc(i);
while less(x,intersect[j]) do dec(j);
if i<=j then begin
y:=intersect; intersect:=intersect[j]; intersect[j]:=y; inc(i); dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

procedure process_line(ix : integer);
var i,j,prc,diff,ii : integer;
ppr : trational_point;
begin
prc:=0;
for i:=1 to ix-1 do if count_intersections(i,ix,ppr) then begin
{if an intersection was found, add it}
inc(prc); intersect[prc]:=ppr;
end;
if prc>0 then sort(1,prc);
{count different intersections}
diff:=prc;
for i:=2 to prc do
if (intersect.x.c*intersect[i-1].x.m=intersect.x.m*intersect[i-1].x.c) and
(intersect.y.c*intersect[i-1].y.m=intersect.y.m*intersect[i-1].y.c) then dec(diff);
parts:=parts+diff+1;

end;
begin
read(n); j:=1;
for i:=1 to n do
begin
read_line(j);
if ok then inc(j);
end;
parts:=1; n:=j-1;
for i:=1 to n do
process_line(i);
writeln(parts);
end.
[/pascal]

[zilnus]

I'm still WA for this problem. Can anyone give test case for me ?
Thanx.GBU

[kapysh]

Anybody, please, help me!!! I don't know where is my mistake.
Formula is: N=k+n+1, where k - number of cutting lines, n - sum of number of different points of intersection with next lines (number of lines are as in input) for every cut line.

Can anybody give me tests?

this is my code
#include <iostream>
#include <cmath>
#include<vector>

using namespace std;

struct point{
double x;
double y;
bool equal(point p){
double dist=sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
if(dist<0.000001)
return true;
return false;
}
};

struct line{
point start,end;
double a,b,c;
};

vector<line> lines;

void intersect(int,int,point&);
void FindAllPoints(int,int&);

int main(){
line l;
int i,j;
int K;//number of tests
int N;//number of lines in current test
int M;//number of points of intersection
int res;
cin>>K;
for(i=0;i<K;i++){
cin>>N;
lines.clear();
for(j=0;j<N;j++){
cin>>l.start.x>>l.start.y>>l.end.x>>l.end.y;
l.a=l.end.y-l.start.y;
l.b=-(l.end.x-l.start.x);
l.c=-l.start.x*l.a-l.start.y*l.b;
lines.push_back(l);
}
M=0;
//clearlines();
for(j=0;j<(N-1);j++)
FindAllPoints(j,M);
if(N)
res=N+1+M;
else
res=1;
if(i)
cout<<endl;
cout<<res<<endl;
}
return 0;
}

void FindAllPoints(int k,int& M){
vector<point> p;
point pp;
int i,j;
for(i=k+1;i<lines.size();i++){
intersect(i,k,pp);
if(pp.x<=0.000001 || pp.x>=999.99999 || pp.y<=0.000001 || pp.y>=999.99999)
continue;
for(j=0;j<p.size();j++)
if(p[j].equal(pp))
break;
if(j==p.size()){
p.push_back(pp);
M++;
}
}
}

void intersect(int j,int k,point& p)
{
double q,w;
if(fabs(lines[j].a*lines[k].b-lines[j].b*lines[k].a)<0.0000001){
p.x=2000.0;
return;
}
q=lines[j].c*lines[k].a-lines[j].a*lines[k].c;
w=lines[j].a*lines[k].b-lines[j].b*lines[k].a;
p.y=q/w;
if(fabs(lines[j].a)>0.0000001){ //not horisontal
q=-lines[j].c-lines[j].b*p.y;
p.x=q/lines[j].a;
}
else{ //horisontal
q=-lines[k].c-lines[k].b*p.y;
p.x=q/lines[k].a;
}
}

[kapysh]

sorry for so bad view of source code. This is more "looking" variant:

Code: Select all

#include <iostream>
#include <cmath>
#include<vector>

using namespace std;

struct point{
	double x;
	double y;
	bool equal(point p){
		double dist=sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
		if(dist<0.000001)
			return true;
		return false;
	}
};

struct line{
	point start,end;
	double a,b,c;
};

vector<line> lines;

void intersect(int,int,point&);
void FindAllPoints(int,int&);

int main(){
	line l;
	int i,j;
	int K;//number of tests
	int N;//number of lines in current test
	int M;//number of points of intersection
	int res;
	cin>>K;
	for(i=0;i<K;i++){
		cin>>N;
		lines.clear();
		for(j=0;j<N;j++){
			cin>>l.start.x>>l.start.y>>l.end.x>>l.end.y;
			l.a=l.end.y-l.start.y;
			l.b=-(l.end.x-l.start.x);
			l.c=-l.start.x*l.a-l.start.y*l.b;
			lines.push_back(l);
		}
		M=0;
		//clearlines();
		for(j=0;j<(N-1);j++)
			FindAllPoints(j,M);
		if(N)
			res=N+1+M;
		else
			res=1;
		if(i)
			cout<<endl;
		cout<<res<<endl;
	}
	return 0;
}

void FindAllPoints(int k,int& M){
	vector<point> p;
	point pp;
	int i,j;
	for(i=k+1;i<lines.size();i++){
		intersect(i,k,pp);
		if(pp.x<=0.000001 || pp.x>=999.99999 || pp.y<=0.000001 || pp.y>=999.99999)
			continue;
		for(j=0;j<p.size();j++)
			if(p[j].equal(pp))
				break;
		if(j==p.size()){
			p.push_back(pp);
			M++;
		}
	}
}

void intersect(int j,int k,point& p)
{
	double q,w;
	if(fabs(lines[j].a*lines[k].b-lines[j].b*lines[k].a)<0.0000001){
		p.x=2000.0;
		return;
	}
	q=lines[j].c*lines[k].a-lines[j].a*lines[k].c;
	w=lines[j].a*lines[k].b-lines[j].b*lines[k].a;
	p.y=q/w;
	if(fabs(lines[j].a)>0.0000001){	//not horisontal
		q=-lines[j].c-lines[j].b*p.y;
		p.x=q/lines[j].a;
	}
	else{							//horisontal
		q=-lines[k].c-lines[k].b*p.y;
		p.x=q/lines[k].a;
	}
}

[volz_kz_g]

I just have submitted this problem 10 times,and can't get AC yet.
I don't know what's wrong with my code.
Maybe who can help me?
there is my code.

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <complex>
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define rrep(i,j,k) for (int i=j;i>=k;--i)
#define x real()
#define y imag()

using namespace std;

const double eps = 1e-10;
const int maxn = 3333;
typedef complex<double> point;
struct _line{point a,b;}line[maxn];
point none,have[maxn];
int m,n,nn,ans,has,had;

int dblcmp(double k)
{
    if (fabs(k) < eps) return 0;
    if (k>0) return 1;
    else return -1;
}

double cross(point a,point b)
{
    return (a.x * b.y - a.y * b.x);
}

double cross(point o,point a,point b)
{
    point oa = a - o;
    point ob = b - o;
    return cross(oa,ob);
}

bool findPoint(point & a,point & b,point & c,point & d,point & e)
{
    point A = b - a;
    point B = d - c;
    point S = c - a;
    if (dblcmp(cross(A,B)) == 0) return false;
    else
	{
	    e = (a + A * cross(S,B) / cross(A,B));
	    if (e.x > 0 && e.x < 1000 && 
		e.y > 0 && e.y < 1000)
		return true;
	    else
		return false;
	}
}

bool cmp(point a,point b)
{
    if (a.x == b.x) return (a.y < b.y);
    else return (a.x < b.x);
}

bool inLine(point a,point b,point c,point d)
{
    int d1 = dblcmp(cross(c,d,a));
    int d2 = dblcmp(cross(c,d,b));
    if (d1 * d2 == 0) return true;
    else return false;
}

bool bound(point a,point b)
{
    if (a.x == b.x && (a.x == 0 || a.x == 1000)) return true;
    if (a.y == b.y && (a.y == 0 || a.y == 1000)) return true;
    return false;
}

int main()
{

    ios::sync_with_stdio(false);
    cin >> m;
    rep(t,1,m)
	{
	    ans = 0;
	    cin >> n;nn = 0;
	    rep(i,1,n) cin >> line[i].a.x >> line[i].a.y
			   >> line[i].b.x >> line[i].b.y;
	    rep(i,1,n) if (!bound(line[i].a,line[i].b)) line[++nn] = line[i];
	    n = nn;

	    rep(i,1,n)
		{
		    rep(j,1,i-1) if (inLine(line[i].a,line[i].b,line[j].a,line[j].b)) continue;
		    has = 0;
		    point tmp;
		    rep(j,1,i-1) 
			{
			    if (findPoint(line[i].a,line[i].b,
					  line[j].a,line[j].b,tmp))
				have[++has] = tmp;
			}
		    had = has;
		    sort(have+1,have+has+1,cmp);
		    rep(j,2,has) if (have[j] == have[j-1]) had--;
		    ans = ans + had + 1;
		}
	    cout << ans+1 << endl;
	    if (t!=m) cout << endl;
	}
    return 0;
}

[brianfry713]

I believe there is a case like this in the judge's input, where a line is repeated:

Code: Select all

2

2
0 0 1000 1000
1000 1000 0 0

2
0 0 1000 1000
0 0 1000 1000

My AC code prints 2 for both.

[volz_kz_g]

I believe there is a case like this in the judge's input, where a line is repeated:

Code: Select all

2

2
0 0 1000 1000
1000 1000 0 0

2
0 0 1000 1000
0 0 1000 1000

My AC code prints 2 for both.

Thank you! I got this bug fixed.
And still get WA,I'm confused.
I check the lines repeated and the lines cover the bound of the cake.
And my output format is write a blank line between two datasets.

this my code now:

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <complex>
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define rrep(i,j,k) for (int i=j;i>=k;--i)
#define x real()
#define y imag()

using namespace std;

const double eps = 1e-10;
const int maxn = 3333;
typedef complex<double> point;
struct _line{point a,b;}line[maxn];
point none,have[maxn],tmp;
int m,n,ans,has,had;

int dblcmp(double k)
{
    if (fabs(k) < eps) return 0;
    if (k>0) return 1;
    else return -1;
}

double cross(point a,point b)
{
    return (a.x * b.y - a.y * b.x);
}

double cross(point o,point a,point b)
{
    point oa = a - o;
    point ob = b - o;
    return cross(oa,ob);
}

bool findPoint(point & a,point & b,point & c,point & d,point & e)
{
    point A = b - a;
    point B = d - c;
    point S = c - a;
    if (dblcmp(cross(A,B)) == 0) return false;
    else
	{
	    e = (a + A * cross(S,B) / cross(A,B));
	    if (e.x > 0 && e.x < 1000 && 
		e.y > 0 && e.y < 1000)
		return true;
	    else
		return false;
	}
}

bool cmp(point a,point b)
{
    if (a.x == b.x) return (a.y < b.y);
    else return (a.x < b.x);
}

bool inLine(point a,point b,point c,point d)
{
    int d1 = dblcmp(cross(c,d,a));
    int d2 = dblcmp(cross(c,d,b));
    if (d1 * d2 == 0) return true;
    else return false;
}

bool bound(point a,point b)
{
    if (a.x == b.x && (a.x == 0 || a.x == 1000)) return true;
    if (a.y == b.y && (a.y == 0 || a.y == 1000)) return true;
    return false;
}

bool same(point a,point b)
{
    if (fabs(b.x - a.x) < eps &&
	fabs(b.y - a.y) < eps) return true;
    else return false;
}

int main()
{
    freopen("test.in","r",stdin);

    ios::sync_with_stdio(false);
    cin >> m;
    rep(t,1,m)
	{
	    ans = 0;
	    cin >> n;
	    rep(i,1,n) cin >> line[i].a.x >> line[i].a.y
			   >> line[i].b.x >> line[i].b.y;

	    rep(i,1,n) if (!bound(line[i].a,line[i].b))
		{
		    bool conti = false;
		    rep(j,1,i-1) if (inLine(line[i].a,line[i].b,line[j].a,line[j].b)) 
			{
			    conti = true;
			    break;
			}
		    if (conti) continue;
		    has = 0;
		    rep(j,1,i-1) 
			{
			    if (findPoint(line[i].a,line[i].b,
					  line[j].a,line[j].b,tmp))
				have[++has] = tmp;
			}
		    had = has;
		    sort(have+1,have+has+1,cmp);
		    rep(j,2,has) if (same(have[j],have[j-1])) had--;
		    ans = ans + had + 1;
		}
	    cout << ans+1 << endl;
	    if (t!=m) cout << endl;
	}
    return 0;
}

[brianfry713]

Don't read from a file. Try input:

Code: Select all

1

2
500 0 1000 1000
500 0 0 1000

AC output 3.

Yes your output formatting is correct.

[volz_kz_g]

Thank you,I found my function to check inLine was wrong.
Thank you again for helping me.