10406 - Cutting tabletops

[madelman]

Anybody has an idea how to do problem 10406? I don't know where to begin.

Any help would be appreciated.

[Dominik Michniewski]

This problem strictly geometric problem. Draw a picture of tabletop before and after cut (first inside second) and see what happend You should use easy math and got Acc

Best regards
DM

[Maniac]

Hmm, I thought this should be an easy one but I keep getting WA. Could somebody please take a look at my code? Am I making a stupid mistake somewhere or are there any tricky cases?

Thanks, Erik

[cpp]#include <stdio.h>
#include <math.h>
#include <assert.h>

#define MAXPOINTS 10000
#define PI (2.0*acos(0.0))

double abs(double a) {
return (a<0?-a:a);
}

class Point {
public:
double x, y;

Point(double nx, double ny) {
x = nx;
y = ny;
}

double dist(Point *p) {
return sqrt((p->x - x)*(p->x - x) + (p->y - y)*(p->y - y));
}
};

class LinePiece {
public:
Point* start;
Point* end;

LinePiece() {}

LinePiece(Point* nstart, Point* nend) {
start = nstart;
end = nend;
}

double length() {
return start->dist(end);
}

double angle(Point *p) {
//returns angle to left of p
//angle in range (-PI, PI]
//angle of PI/2 means perpendicular and to left, -PI/2 means to right
double cross = (end->x - start->x)*(p->y - start->y) - (end->y - start->y)*(p->x - start->x);
double angle = asin(cross/(start->dist(end)*start->dist(p)));

if((p->x - end->x)*(start->x - end->x) + (p->y - end->y)*(start->y - end->y) < 0) {
if(cross > 0) angle+= PI/2;
else angle-= PI/2;
}
return angle;
}
};

class Polygon {
public:
int n;
Point* point[MAXPOINTS];

Polygon() {
n = 0;
}

double area() {
double a = 0;
if(n > 2) {
int i;
for(i=1; i<n; i++)
a+= 0.5*(double)((point[i-1]->x * point->y) - (point->x * point[i-1]->y));
a+= 0.5*(double)((point[n-1]->x * point[0]->y) - (point[0]->x * point[n-1]->y));
}
return abs(a);
}
};

int n;
double thickness;
Polygon *pol;

Point* getP(int i) {
return pol->point[(i + n) % n];
}

void doit() {
int i;
double x,y;
pol->n = n;
for(i=0; i<n; i++) {
scanf("%lf%lf", &x, &y);
pol->point->x = x;
pol->point->y = y;
}

double area = pol->area();

double side;
LinePiece l;

for(i=0; i<n; i++) {
l.start = getP(i);
l.end = getP(i + 1);
double angle = (PI - abs(l.angle(getP(i - 1))))/2.0;
side = abs(thickness*tan(angle));

area -= thickness * l.length();
area += thickness * side;
}
printf("%.3lf\n", area);
}

int main() {
pol = new Polygon();
int i;
for(i=0; i<MAXPOINTS; i++)
pol->point = new Point(0.0,0.0);

scanf("%lf%ld", &thickness, &n);
while(thickness != 0.0 || n != 0) {
doit();
scanf("%lf%ld", &thickness, &n);
}
return 0;
}
[/cpp]

[Willar]

I keep getting WA... Is it possible for an admin to post some test cases? I'm losing my mind here

My idea:

I move the polygon sides 'd' centimeters through the inside, and then compute the intersections, being these the new vertices. Then, sum all sub-triangle's areas.

[cpp]
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef pair<double, double> punto;
typedef pair<punto, punto> segmento;

segmento corre(punto p, punto q, double d){
punto w = make_pair(q.first - p.first, q.second - p.second);
punto v = make_pair(w.second, -w.first);
double l = v.first * v.first + v.second * v.second;
l = sqrt(l);
v.first = (v.first * d) / l;
v.second = (v.second * d) / l;
p.first += v.first; p.second += v.second;
q.first += v.first; q.second += v.second;
return make_pair(p,q);
}

punto interseccion(segmento a, segmento b){
// segmento a: puntos P y Q. segmento b: puntos R y S. interseccion, T
// NO SON PARALELOS SINO SE PUDRE MALA ONDA EH
double yqp, xsr, xpr, xqp, yrp, ysr,xr,yr,xp,yp;
yqp = a.second.second - a.first.second;
xsr = b.second.first - b.first.first;
xpr = a.first.first - b.first.first;
xqp = a.second.first - a.first.first;
yrp = b.first.second - a.first.second;
ysr = b.second.second - b.first.second;
xp = a.first.first;
yp = a.first.second;
xr = b.first.first;
yr = b.first.second;

double xt;
double yt;

xt = (yqp * xsr * xp - ysr * xqp * xr + xqp * xsr * yrp) / (yqp * xsr - ysr * xqp);
if(abs(xqp)<abs(xsr)){
yt = (xt - xr) * ysr / xsr + yr;
} else {
yt = (xt - xp) * yqp / xqp + yp;
}
return make_pair(xt, yt);
}

double area(punto q, punto p1, punto p2) {
p1.first -= q.first;
p1.second -= q.second;
p2.first -= q.first;
p2.second -= q.second;
return (p1.first*p2.second)-(p2.first*p1.second);
}

int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","rt",stdin);
#endif

double d;
long n;
cin>>d>>n;
while((d!=0)||(n!=0)){
vector <punto> p;
vector <segmento> m;
if(n<3){
cout<<"0.000"<<endl;
double x,y;
for(long i=0; i<n; i++) cin>>x>>y;
} else {
for(long i=0; i<n; i++){
double x,y;
cin>>x>>y;
p.push_back(make_pair(x,y));
}
for(long i=0; i<n; i++){
m.push_back(corre(p, p[(i+1)%n], d));
}
for(long i=0; i<n; i++){
p = interseccion(m, m[(i+1)%n]);
}
double a = 0;
for(long i=0; i<n; i++){
a+= (area(p[1], p[0], p));
}
a /= 2;
printf("%.3lf\n",a);
}
cin>>d>>n;
}

return 0;
}

[/cpp]

[Willar]

LOL

area(p[1], p[0], p)

this should have been

area(p[0], p[(i+1)%n], p)

Accepted after this

[zid_adrenalyns]

hi Willar, I have some doubts for this problem.

What happen if the width d (to be cut off) is greater than the smallest distance between the center and an edge of the polygon?

the area should be negative or i would be print "0.000"?

what is the output for this input:

Code: Select all

2 4 0 0 0 5 5 5 5 0
1 3 0 0 0 5 5 0
1 3 0 0 3 5.1961524 6 0
3 4 0 -10 -10 0 0 10 10 0
10 4 120.0 100.0 120.0 160.0 180.0 160.0 180.0 100.0
15 4 140.0 120.0 140.0 140.0 160.0 140.0 160.0 120.0
0 0

check the last line. Thanks.

[Darko]

My AC program outputs this for that input:

Code: Select all

1.000
1.257
2.785
66.294
1600.000
100.000

[zid_adrenalyns]

I don't understand, the problem seems similar to offset polygon.
I'm only add this line:

offset*= -1;

the logic is the same or have any special case?

[Darko]

Yes, that is the only difference in my program (and output, of course).
(actually, I do -d, instead of -1*d, there might be a difference, but I think mine should be wrong in that case)

It says this, too:

d is much smaller than any of the sides of the polygon

So there are no cases like the last one in your previous post.

Make some cases and we can compare output.

[Jan]

Why the judge returns WA for the following code? I have written another version (different approach) which was 'Accepted'. But haven't found why this code is wrong. Hope anyone helps. Thanks in advance.

Code: Select all

Removed the spoiler...

[little joey]

I can't say I fully understand your code. What seems a bit strange to me, is that your function process() only considers the first 4 points. Anyway, for this input:

Code: Select all

2 5 0 10 0 20 10 50 45 33 30 0
0 0

your program outputs 1183.137, while the correct answer is 1123.782.

Happy hunting.


On second thought:
You take the ratio of the lengths of an arbitrary side before and after the cut, and expect that the area of polygon shrinks as the square of this ratio. This can't be correct, because this ratio is not constant between the sides of the polygon; that is: if you would take another side of the polygon, the ratio would be different.

[Jan]

On second thought:
You take the ratio of the lengths of an arbitrary side before and after the cut, and expect that the area of polygon shrinks as the square of this ratio. This can't be correct, because this ratio is not constant between the sides of the polygon; that is: if you would take another side of the polygon, the ratio would be different.

Thanks a lot. Got it. . May be the property only works for triangle. Thanks again.