Page 1 of 1
527 - What is the idea?
Posted: Sat Aug 03, 2002 9:51 pm
by medv
Can smb tell me the idea of solving this task? (The partition of a cake)
Re: 527 - What is the idea?
Posted: Wed Aug 07, 2002 9:39 am
by 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
527 run time error...
Posted: Wed Feb 26, 2003 8:57 pm
by 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.
527
Posted: Mon Jan 26, 2004 7:02 pm
by 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]
527 WA : Can give simple input ?
Posted: Thu Oct 28, 2004 1:21 pm
by zilnus
I'm still WA for this problem. Can anyone give test case for me ?
Thanx.GBU
527 WA
Posted: Tue Oct 24, 2006 8:36 pm
by 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;
}
}
Posted: Tue Oct 24, 2006 8:42 pm
by 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;
}
}
527 - The partition of a cake
Posted: Tue Jan 15, 2013 6:13 am
by 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;
}
Re: 527 ?
Posted: Tue Jan 15, 2013 11:45 pm
by 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.
Re: 527 ?
Posted: Wed Jan 16, 2013 5:06 am
by volz_kz_g
brianfry713 wrote: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;
}
Re: 527 ?
Posted: Wed Jan 16, 2013 10:43 pm
by brianfry713
Don't read from a file. Try input:
AC output 3.
Yes your output formatting is correct.
Re: 527 ?
Posted: Thu Jan 17, 2013 2:58 am
by volz_kz_g
Thank you,I found my function to check inLine was wrong.
Thank you again for helping me.