218 - Moth Eradication
Moderator: Board moderators
Can you please send me the code to solve Moth Eradication ?
Can you please send me the code to solve Moth Eradication ?
218
I programmed a solution in Java and then found out that the Collections Framework isn't supported, so I redid it in C++. Now it is saying that my output is exceeding the limit. I says this even if I have the program only output the Region # line for each set. If someone could help me understand what is causing this I would appreciate it.
[cpp]/* @JUDGE_ID: 43982PR 218 C++*/
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
void sortPoints(int, int, double[][2]);
void updateUpperPath(int, vector<int>&, double[][2]);
void updateLowerPath(int, vector<int>&, double[][2]);
int main() {
int curNum = 1;
int numPoints;
cin >> numPoints;
while (numPoints != 0) {
double thePoints[100][2];
for (int i = 0; i < numPoints; i++) {
cin >> thePoints[0];
cin >> thePoints[1];
}
cout << "Region #" << curNum << ":";
sortPoints(0, numPoints - 1, thePoints);
vector<int> upperPath, lowerPath;
if(numPoints != 1) {
upperPath.push_back(1);
upperPath.push_back(0);
lowerPath.push_back(1);
lowerPath.push_back(0);
for (int j = 2; j < numPoints; j++) {
upperPath.insert(upperPath.begin(),j);
lowerPath.insert(lowerPath.begin(),j);
updateUpperPath(numPoints,upperPath,thePoints);
updateLowerPath(numPoints,lowerPath,thePoints);
}
}
else {
upperPath.push_back(0);
lowerPath.push_back(0);
}
double totalLength = 0.0;
int upsize = upperPath.size();
int lowsize = lowerPath.size();
for (int d = 0; d < upsize; d++) {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[upperPath[upsize - d - 1]][0] << "," <<
thePoints[upperPath[upsize - d - 1]][1];
if(upsize != 1) cout << ")-";
else cout << ")\n";
if (d > 0)
totalLength += sqrt(pow(thePoints[upperPath[upsize - d - 1]][0] -
thePoints[upperPath[upsize - d]][0], 2.0) +
pow(thePoints[upperPath[upsize - d - 1]][1] -
thePoints[upperPath[upsize - d]][1], 2.0));
}
for (int e = 1; e < lowsize; e++) {
if (e == lowsize - 1) {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[lowerPath[e]][0] << "," <<
thePoints[lowerPath[e]][1] << ")\n";
}
else {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[lowerPath[e]][0] << "," <<
thePoints[lowerPath[e]][1] << ")-";
}
if(numPoints > 2)totalLength += sqrt(pow(thePoints[lowerPath[e]][0] -
thePoints[lowerPath[e - 1]][0], 2.0) +
pow(thePoints[lowerPath[e]][1] -
thePoints[lowerPath[e - 1]][1], 2.0));
}
cout << "Perimeter length = " << setprecision(2) <<
setiosflags(ios::fixed | ios::showpoint) << totalLength << "\n\n";
curNum++;
cin >> numPoints;
}
return 0;
}
void sortPoints(int start, int end, double thePoints[][2]) {
if(end - start <= 0) return;
int half = (end-start)/2+start, newStart = (end-start)/2+start+1;
sortPoints(start,half,thePoints);
sortPoints(newStart,end,thePoints);
double temp[100][2];
int first = start, second = newStart, i = 0;
while(first <= half && second <= end) {
if(thePoints[first][0] <= thePoints[second][0]) {
temp[0] = thePoints[first][0];
temp[1] = thePoints[first][1];
first++;
}
else {
temp[0] = thePoints[second][0];
temp[1] = thePoints[second][1];
second++;
}
i++;
}
if(first > half) {
while(second <= end) {
temp[0] = thePoints[second][0];
temp[1] = thePoints[second][1];
second++;
i++;
}
}
else {
while(first <= half) {
temp[0] = thePoints[first][0];
temp[1] = thePoints[first][1];
first++;
i++;
}
}
i = 0;
for(int n = start; n <= end; n++) {
thePoints[n][0] = temp[i][0];
thePoints[n][1] = temp[i][1];
i++;
}
}
void updateUpperPath(int numPoints, vector<int>& upperPath, double thePoints[][2]) {
for(int m = 0; m < upperPath.size()-2; m++) {
if( thePoints[upperPath[m]][0] *
(thePoints[upperPath[m+1]][1] - thePoints[upperPath[m+2]][1]) -
thePoints[upperPath[m]][1] *
(thePoints[upperPath[m+1]][0] - thePoints[upperPath[m+2]][0]) +
thePoints[upperPath[m+1]][0] * thePoints[upperPath[m+2]][1] -
thePoints[upperPath[m+1]][1] * thePoints[upperPath[m+2]][0] <= 0) {
upperPath.erase(upperPath.begin() + (m+1));
m--;
}
else
return;
}
}
void updateLowerPath(int numPoints, vector<int>& lowerPath, double thePoints[][2]) {
for(int m = 0; m < lowerPath.size()-2; m++) {
if( thePoints[lowerPath[m]][0] *
(thePoints[lowerPath[m+1]][1] - thePoints[lowerPath[m+2]][1]) -
thePoints[lowerPath[m]][1] *
(thePoints[lowerPath[m+1]][0] - thePoints[lowerPath[m+2]][0]) +
thePoints[lowerPath[m+1]][0] * thePoints[lowerPath[m+2]][1] -
thePoints[lowerPath[m+1]][1] * thePoints[lowerPath[m+2]][0] >= 0) {
lowerPath.erase(lowerPath.begin() + (m+1));
m--;
}
else
return;
}
}[/cpp]
Thanks
[cpp]/* @JUDGE_ID: 43982PR 218 C++*/
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
void sortPoints(int, int, double[][2]);
void updateUpperPath(int, vector<int>&, double[][2]);
void updateLowerPath(int, vector<int>&, double[][2]);
int main() {
int curNum = 1;
int numPoints;
cin >> numPoints;
while (numPoints != 0) {
double thePoints[100][2];
for (int i = 0; i < numPoints; i++) {
cin >> thePoints[0];
cin >> thePoints[1];
}
cout << "Region #" << curNum << ":";
sortPoints(0, numPoints - 1, thePoints);
vector<int> upperPath, lowerPath;
if(numPoints != 1) {
upperPath.push_back(1);
upperPath.push_back(0);
lowerPath.push_back(1);
lowerPath.push_back(0);
for (int j = 2; j < numPoints; j++) {
upperPath.insert(upperPath.begin(),j);
lowerPath.insert(lowerPath.begin(),j);
updateUpperPath(numPoints,upperPath,thePoints);
updateLowerPath(numPoints,lowerPath,thePoints);
}
}
else {
upperPath.push_back(0);
lowerPath.push_back(0);
}
double totalLength = 0.0;
int upsize = upperPath.size();
int lowsize = lowerPath.size();
for (int d = 0; d < upsize; d++) {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[upperPath[upsize - d - 1]][0] << "," <<
thePoints[upperPath[upsize - d - 1]][1];
if(upsize != 1) cout << ")-";
else cout << ")\n";
if (d > 0)
totalLength += sqrt(pow(thePoints[upperPath[upsize - d - 1]][0] -
thePoints[upperPath[upsize - d]][0], 2.0) +
pow(thePoints[upperPath[upsize - d - 1]][1] -
thePoints[upperPath[upsize - d]][1], 2.0));
}
for (int e = 1; e < lowsize; e++) {
if (e == lowsize - 1) {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[lowerPath[e]][0] << "," <<
thePoints[lowerPath[e]][1] << ")\n";
}
else {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[lowerPath[e]][0] << "," <<
thePoints[lowerPath[e]][1] << ")-";
}
if(numPoints > 2)totalLength += sqrt(pow(thePoints[lowerPath[e]][0] -
thePoints[lowerPath[e - 1]][0], 2.0) +
pow(thePoints[lowerPath[e]][1] -
thePoints[lowerPath[e - 1]][1], 2.0));
}
cout << "Perimeter length = " << setprecision(2) <<
setiosflags(ios::fixed | ios::showpoint) << totalLength << "\n\n";
curNum++;
cin >> numPoints;
}
return 0;
}
void sortPoints(int start, int end, double thePoints[][2]) {
if(end - start <= 0) return;
int half = (end-start)/2+start, newStart = (end-start)/2+start+1;
sortPoints(start,half,thePoints);
sortPoints(newStart,end,thePoints);
double temp[100][2];
int first = start, second = newStart, i = 0;
while(first <= half && second <= end) {
if(thePoints[first][0] <= thePoints[second][0]) {
temp[0] = thePoints[first][0];
temp[1] = thePoints[first][1];
first++;
}
else {
temp[0] = thePoints[second][0];
temp[1] = thePoints[second][1];
second++;
}
i++;
}
if(first > half) {
while(second <= end) {
temp[0] = thePoints[second][0];
temp[1] = thePoints[second][1];
second++;
i++;
}
}
else {
while(first <= half) {
temp[0] = thePoints[first][0];
temp[1] = thePoints[first][1];
first++;
i++;
}
}
i = 0;
for(int n = start; n <= end; n++) {
thePoints[n][0] = temp[i][0];
thePoints[n][1] = temp[i][1];
i++;
}
}
void updateUpperPath(int numPoints, vector<int>& upperPath, double thePoints[][2]) {
for(int m = 0; m < upperPath.size()-2; m++) {
if( thePoints[upperPath[m]][0] *
(thePoints[upperPath[m+1]][1] - thePoints[upperPath[m+2]][1]) -
thePoints[upperPath[m]][1] *
(thePoints[upperPath[m+1]][0] - thePoints[upperPath[m+2]][0]) +
thePoints[upperPath[m+1]][0] * thePoints[upperPath[m+2]][1] -
thePoints[upperPath[m+1]][1] * thePoints[upperPath[m+2]][0] <= 0) {
upperPath.erase(upperPath.begin() + (m+1));
m--;
}
else
return;
}
}
void updateLowerPath(int numPoints, vector<int>& lowerPath, double thePoints[][2]) {
for(int m = 0; m < lowerPath.size()-2; m++) {
if( thePoints[lowerPath[m]][0] *
(thePoints[lowerPath[m+1]][1] - thePoints[lowerPath[m+2]][1]) -
thePoints[lowerPath[m]][1] *
(thePoints[lowerPath[m+1]][0] - thePoints[lowerPath[m+2]][0]) +
thePoints[lowerPath[m+1]][0] * thePoints[lowerPath[m+2]][1] -
thePoints[lowerPath[m+1]][1] * thePoints[lowerPath[m+2]][0] >= 0) {
lowerPath.erase(lowerPath.begin() + (m+1));
m--;
}
else
return;
}
}[/cpp]
Thanks
218-Moth Eradication - Some tricky cases?
Code: Select all
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct
{
float x;
float y;
float theta;
}point;
int compare( const void *arg1, const void *arg2 );
int cw( point *p1, point *p2, point *p );
float theta( point *p1, point *p2 );
float fabs( float x );
int graham( void );
float dist( point *p1, point *p2 );
int npts=0;
point pts[2000];
using namespace std;
int main( int argc, char *argv[] )
{
int m;
int i;
point t;
int case_count=0;
float perimeter;
fscanf( stdin, "%d", &npts );
while ( npts > 0 )
{
for ( i=0;i<npts;i++ )
{
fscanf( stdin, "%f %f", &pts[i].x, &pts[i].y );
}
if ( npts > 2 )
{
m = 0;
for ( i=1;i<npts;i++ )
{
if ( pts[i].y < pts[m].y )
m = i;
else if ( pts[i].y == pts[m].y && pts[i].x < pts[m].x )
m = i;
}
t = pts[0];
pts[0] = pts[m];
pts[m] = t;
for ( i=1;i<npts;i++ )
pts[i].theta = theta( &pts[0], &pts[i] );
qsort( &pts[1], npts-1, sizeof(point), compare );
m = graham( );
} else { m=npts-1; }
perimeter = 0;
case_count++;
fprintf( stdout, "Region #%d:\n", case_count );
for ( i=m;i>=0;i-- )
{
if ( i != 0 )
perimeter += dist( &pts[i], &pts[i-1] );
fprintf( stdout, "(%.1f,%.1f)-", pts[i].x, pts[i].y );
}
fprintf( stdout, "(%.1f,%.1f)\n", pts[m].x, pts[m].y );
perimeter += dist( &pts[0], &pts[m] );
fprintf( stdout, "Perimeter length = %.2f\n\n", perimeter );
fscanf( stdin, "%d", &npts );
}
return 0;
}
int compare( const void *arg1, const void *arg2 )
{
point *p1, *p2;
p1 = (point*)arg1;
p2 = (point*)arg2;
if ( p1->theta < p2->theta )
return -1;
if ( p1->theta == p2->theta )
{
if ( dist( &pts[0], p1 ) < dist( &pts[0], p2 ) )
return -1;
else
return 1;
}
return 1;
}
float dist( point *p1, point *p2 )
{
return sqrt((p1->x-p2->x)*(p1->x-p2->x)+(p1->y-p2->y)*(p1->y-p2->y));
}
int cw( point *p1, point *p2, point *p )
{
float cross;
cross = (p2->x-p1->x)*(p->y-p1->y)-(p2->y-p1->y)*(p->x-p1->x);
if ( cross > 0 ) /* clock-wise */
return 1;
else if ( cross == 0 ) /* co-linear */
return 0;
else /* counter-clockwise */
return -1;
}
float fabs( float x )
{
if ( x < 0 )
return -x;
return x;
}
float theta( point *p1, point *p2 )
{
float dx,dy,ax,ay;
float t;
dx = p2->x-p1->x;
dy = p2->y-p1->y;
ax = fabs( dx );
ay = fabs( dy );
if ( ax == 0 && ay == 0 )
t = 0;
else
t = dy/(ax+ay);
if ( dx < 0 )
t = 2 - t;
else if ( dy < 0 )
t = 4 + t;
return t * 90.0f;
}
int graham( void )
{
int m=2;
int l=npts-1;
int i;
point t;
stack<point> ps;
for ( i=3;i<npts;i++ )
{
while( cw( &pts[m-1], &pts[m], &pts[i] )==-1 )
{
ps.push( pts[m] );
m = m - 1;
}
m = m + 1;
pts[m] = pts[i];
}
while ( !ps.empty( ) )
{
t = ps.top( );
ps.pop( );
if ( cw( &pts[m-1], &pts[m], &t )>=0 )
{
m = m + 1;
pts[m] = t;
}
else
{
pts[l] = t;
l = l - 1;
}
}
if ( cw( &pts[m-1], &pts[0], &pts[m] ) == 1 )
m = m-1;
return m;
}
but always got WA from the judge.
Is it because some special cases? Or there is something else....?
2 things:
1. don't use float, use double
2. the problem data is sensitive to precision error, write something like:
1. don't use float, use double
2. the problem data is sensitive to precision error, write something like:
Code: Select all
if ( cross > 1e-8 ) /* clock-wise */
return 1;
else if ( cross < -1e-8 ) /* counterclockwise */
return -1;
else
return 0
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
218 - Moth Eradication
I have getting WA on problem 218.
Can someone give me some test cases??
Thanks in advance.
![:-?](./images/smilies/icon_confused.gif)
Can someone give me some test cases??
Thanks in advance.
Ami ekhono shopno dekhi...
HomePage
HomePage
Did you try this
This should give a perimeter length of 8.
Code: Select all
9
1 -1
1 0
1 1
0 1
0 -1
0 0
-1 1
-1 -1
-1 0
There's no need to get fancy here, and there are no tricky cases. This problem should be solved easily with prewritten codes. If your convex hull code can output in clockwise order including the collinear points, then it should get AC. Otherwise, consider rewriting the convex hull code, there's probably something wrong with the convex hull code.
Try changing this line:
to
You're not handling collinear points properly.
Code: Select all
if (surf(c[k-1], c[k], a[i]) != 1)
Code: Select all
if (surf(c[k-1], c[k], a[i]) == -1)
218- Moth Eradication again...
Hi, fellows!
I apologise for commencing a new discussion on "Moth Eradication" seeing that a great deal was said on it as it is, but I do hope that if supported by you it will be of considerable value for most of us. I've already read all that was written here ever since 2001, my code successfully passes all tricky cases which are present here, but invariably gets WA by the Judge....
If you construct a test case in which my code fails, I'd be grateful very much, as I myself have already tried all the cases I could think of![:)](./images/smilies/icon_smile.gif)
Come to my assistance, please, and let's make this stuff acceptable![:)](./images/smilies/icon_smile.gif)
I apologise for commencing a new discussion on "Moth Eradication" seeing that a great deal was said on it as it is, but I do hope that if supported by you it will be of considerable value for most of us. I've already read all that was written here ever since 2001, my code successfully passes all tricky cases which are present here, but invariably gets WA by the Judge....
If you construct a test case in which my code fails, I'd be grateful very much, as I myself have already tried all the cases I could think of
![:)](./images/smilies/icon_smile.gif)
Come to my assistance, please, and let's make this stuff acceptable
![:)](./images/smilies/icon_smile.gif)
Code: Select all
/#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Epsilon 1e-6
#define N 1003
typedef
struct point{
double x;
double y;
}point;
typedef
struct vertice{
double ang;
double d;
double x;
double y;
}vertice;
point p[N];
point S[N];
int top;
vertice *v;
int compare_points1(const void *a, const void *b);
int compare_points2(const void *a, const void *b);
int compare_vertices1(const void *a,const void *b);
int compare_vertices2(const void *a,const void *b);
double distance(point *A, point *B);
int is_left_turn(point *p1,point *p2,point *p3);
void Graham_Scan_left(int k);
void Graham_Scan_right(int k);
void init();
void push(point A);
void pop();
void get_top(point *A);
void next_to_top(point *A);
point southpole,northpole;
point contour[N];
int j;
int main()
{
int n;
int t,k;
int test=0;
double Perimeter;
FILE *in=freopen("218.in","r",stdin);
scanf("%d",&n);
while(n)
{
for(t=0;t<n;t++)
scanf("%lf %lf",&p[t].x,&p[t].y);
qsort(p,n,sizeof(point),compare_points2);
northpole=p[0];
qsort(p,n,sizeof(point),compare_points1);
southpole=p[0];
v=malloc((n+1)*sizeof(vertice));
for(t=0;t<n-1;t++)
{
v[t].x=p[t+1].x;
v[t].y=p[t+1].y;
v[t].d=distance(&p[0],&p[t+1]);
v[t].ang=(v[t].x-p[0].x)/v[t].d;
}
qsort(v,n-1,sizeof(vertice),compare_vertices1);
for(t=0;t<n-1;t++)
{
p[t+1].x=v[t].x;
p[t+1].y=v[t].y;
}
for(t=0;t<n;t++)
if(fabs(p[t].x-northpole.x)<Epsilon && fabs(p[t].y-northpole.y)<Epsilon)
{
k=t;
break;
}
Graham_Scan_left(k);
printf("Region #%d:\n",++test);
for(t=top;t>=0;t--)
{
contour[top-t]=S[t];
}
j=top;
qsort(v,n-1,sizeof(vertice),compare_vertices2);
for(t=0;t<n-1;t++)
{
p[t+1].x=v[t].x;
p[t+1].y=v[t].y;
}
for(t=0;t<n;t++)
if(fabs(p[t].x-northpole.x)<Epsilon && fabs(p[t].y-northpole.y)<Epsilon)
{
k=t;
break;
}
Graham_Scan_right(k);
for(t=1;t<=top;t++)
{
contour[++j]=S[t];
}
for(t=0;t<j;t++)
printf("(%.1lf,%.1lf)-",contour[t].x,contour[t].y);
printf("(%.1lf,%.1lf)\n",contour[j].x,contour[j].y);
Perimeter=0;
for(t=0;t<j;t++)
Perimeter+=distance(&contour[t],&contour[t+1]);
printf("Perimeter length = %.2lf\n",Perimeter);
free(v);
scanf("%d",&n);
if(n)
printf("\n");
else
break;
}
return 0;
}
int compare_points1(const void *a, const void *b)
{
point *s=(point*)a;
point *t=(point*)b;
if(fabs(s->y-t->y)>Epsilon)
{
if(s->y<t->y)
return -1;
else
return 1;
}
else
{
if(fabs(s->x-t->x)>Epsilon)
{
if(s->x<t->x)
return -1;
else
return 1;
}
else
return 0;
}
}
int compare_points2(const void *a, const void *b)
{
point *s=(point*)a;
point *t=(point*)b;
if(fabs(s->y-t->y)>Epsilon)
{
if(s->y>t->y)
return -1;
else
return 1;
}
else
{
if(fabs(s->x-t->x)>Epsilon)
{
if(s->x>t->x)
return -1;
else
return 1;
}
else
return 0;
}
}
int compare_vertices1(const void *a,const void *b)
{
vertice *s=(vertice*)a;
vertice *t=(vertice*)b;
if(fabs(s->ang-t->ang)>Epsilon)
{
if(s->ang>t->ang)
return -1;
else
return 1;
}
else
{
if(fabs(s->d-t->d)>Epsilon)
{
if(s->d<t->d)
return -1;
else
return 1;
}
else
return 0;
}
}
int compare_vertices2(const void *a,const void *b)
{
vertice *s=(vertice*)a;
vertice *t=(vertice*)b;
if(fabs(s->ang-t->ang)>Epsilon)
{
if(s->ang<t->ang)
return -1;
else
return 1;
}
else
{
if(fabs(s->d-t->d)>Epsilon)
{
if(s->d<t->d)
return -1;
else
return 1;
}
else
return 0;
}
}
double distance(point *A, point *B)
{
double tmp1,tmp2;
tmp1=(A->x-B->x);
tmp2=(A->y-B->y);
return sqrt(tmp1*tmp1+tmp2*tmp2);
}
int is_left_turn(point *p1,point *p2,point *p3)
{
double tmp1,tmp2;
tmp1=(p2->x-p1->x)*(p3->y-p1->y);
tmp2=(p2->y-p1->y)*(p3->x-p1->x);
if(fabs(tmp1-tmp2)>Epsilon)
{
if(tmp1>tmp2)
return 1;
else
return 0;
}
else
return 1;
}
void Graham_Scan_left(int k)
{
int t;
point p1,p2;
init();
for(t=0;t<=((k>2)?(2):(k));t++)
push(p[t]);
for(t=3;t<=k;t++)
if(top>=1)
{
next_to_top(&p1);
get_top(&p2);
while(top>=2 && (!is_left_turn(&p1,&p2,&p[t])))
{
pop();
next_to_top(&p1);
get_top(&p2);
}
push(p[t]);
}
else
push(p[t]);
}
int is_right_turn(point *p1,point *p2,point *p3)
{
double tmp1,tmp2;
tmp1=(p2->x-p1->x)*(p3->y-p1->y);
tmp2=(p2->y-p1->y)*(p3->x-p1->x);
if(fabs(tmp1-tmp2)>Epsilon)
{
if(tmp1<tmp2)
return 1;
else
return 0;
}
else
return 1;
}
void Graham_Scan_right(int k)
{
int t;
point p1,p2;
init();
for(t=0;t<=((k>2)?(2):(k));t++)
push(p[t]);
for(t=3;t<=k;t++)
if(top>=1)
{
next_to_top(&p1);
get_top(&p2);
while(top>=2 && (!is_right_turn(&p1,&p2,&p[t])))
{
pop();
next_to_top(&p1);
get_top(&p2);
}
push(p[t]);
}
else
push(p[t]);
}
void init()
{
top=-1;
}
void push(point A)
{
top++;
S[top]=A;
}
void pop()
{
top--;
}
void next_to_top(point *A)
{
*A=S[top-1];
}
void get_top(point *A)
{
*A=S[top];
}
218 - WA
Please, give me some test data for this problem.
Code: Select all
#include <stdio.h>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std ;
#define EPS 1e-7
struct P { double x, y; P() {}; P( double q, double w ) : x( q ), y( w ) {} };
P operator - ( const P &p, const P &q ) { P u( p.x - q.x, p.y - q.y ); return u; }
bool operator !=( const P &p, const P &q ) { return fabs(p.x - q.x)>EPS || fabs(p.y - q.y)>EPS;}
vector<P> JarvisMarch ( vector<P> Q )
{
vector<P> S ;
P p, q ;
int i, n ;
n = Q.size( ) ;
p = Q[0] ;
for ( i=1; i<n; i++ )
if ( Q[i].y < p.y-EPS )
p = Q[i] ;
else
if ( fabs( Q[i].y - p.y ) < EPS )
if ( Q[i].x < p.x-EPS )
p = Q[i] ;
do
{
S.push_back ( p ) ;
p = Q[0] ;
q = S.back( ) ;
for ( i=1; i<n; i++ )
p = ( Q[i] - q ).x * ( p - q ).y - ( Q[i] - q ).y * ( p - q ).x > EPS ||
( fabs(( Q[i] - q ).x * ( p - q ).y - ( Q[i] - q ).y * ( p - q ).x) < EPS && ( Q[i] - q ).x * ( Q[i] - q ).x + ( Q[i] - q ).y * ( Q[i] - q ).y >
( p - q ).x * ( p - q ).x + ( p - q ).y * ( p - q ).y+EPS ) ? Q[i] : p ;
}
while ( p != S[0] ) ;
return S ;
}
vector<P> Q ;
void main() {
P p ;
int n,it,i,j;
double perimeter ;
it=1;
while ( scanf ( "%d", &n ),n ) {
Q.clear ( ) ;
for(i=0; i<n; i++) {
scanf("%lf%lf",&p.x,&p.y) ;
Q.push_back ( p ) ;
}
Q = JarvisMarch ( Q ) ;
n = Q.size ( ) ;
perimeter = 0.0 ;
for ( i=n-1,j=0; j<n; i=j++ )
perimeter += sqrt ( (Q[i].x-Q[j].x)*(Q[i].x-Q[j].x) + (Q[i].y-Q[j].y)*(Q[i].y-Q[j].y) ) ;
printf ( "Region #%d:\n(%.1lf,%.1lf)", it++,Q[0].x+EPS,Q[0].y+EPS ) ;
for ( i=n-1; i>=0; i-- ) printf ( "-(%.1lf,%.1lf)", Q[i].x+EPS, Q[i].y+EPS ) ;
putchar( '\n' ) ;
printf ( "Perimeter length = %.2lf\n\n", perimeter+EPS ) ;
}
}
Narek Saribekyan
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- Contact:
Try this input:
My Accepted code give this output:
hope it helps
Code: Select all
8
0 0
.5 0
1 0
1 .5
1 1
.5 1
0 1
0 .5
0
Code: Select all
Region #1:
(0.0,1.0) - (0.5,1.0) - (1.0,1.0) - (1.0,0.5) - (1.0,0.0) - (0.5,0.0) - (0.0,0.0) - (0.0,1.0)
Perimeter length = 4.00
There was some threads on this topic like:
http://online-judge.uva.es/board/viewt ... light=218
try them!
http://online-judge.uva.es/board/viewt ... light=218
try them!