Databases
StackOverflow2013
Postsdbo
POWhy isn't my convex hull perimeter calculation working?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy isn't my convex hull perimeter calculation working?
    primarykey
    data
    text
    <p>Input: set of Points Output: perimeter of convex hull made from these points</p> <p>I don't why, but I'm still getting bad perimeter on some inputs (I don't know which inputs). Can you please tell me if there is something bad im my alghorithm? (or implementation)</p> <pre><code>#include&lt;iostream&gt; #include&lt;vector&gt; #include&lt;algorithm&gt; #include&lt;cmath&gt; #include&lt;iomanip&gt; using namespace std; struct Point{ int x; int y; bool operator&lt;(const Point &amp;p)const { return (x&lt;p.x || (x==p.x &amp;&amp; y&lt;p.y)); } }; long long cross(Point A, Point B, Point C) { return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); } vector&lt;Point&gt; ConvexHull(vector&lt;Point&gt; P) //Andrew's monotone chain { vector&lt;Point&gt; H; //hull H.resize(2*P.size()); int k=0; if(P.size()&lt;3) return H; sort(P.begin(),P.end()); //lower for(int i=0;i&lt;P.size();i++) { while(k&gt;=2 &amp;&amp; cross(H[k-2],H[k-1],P[i])&lt;=0) k--; H[k]=P[i]; k++; } int t=k+1; //upper for(int i=P.size()-2; i&gt;=0 ;i--) { while(k&gt;=t &amp;&amp; cross(H[k-2],H[k-1],P[i])&lt;=0) k--; H[k]=P[i]; k++; } H.resize(k); return H; }; double perimeter(vector&lt;Point&gt; P) { double r=0; for(int i=1;i&lt;P.size();i++) r+=sqrt(pow(P[i].x-P[i-1].x,2)+pow(P[i].y-P[i-1].y,2)); return r; } int main(){ int N; cin&gt;&gt;N; vector&lt;Point&gt;P; P.resize(N); for(int i=0;i&lt;N;i++) cin&gt;&gt;P[i].x&gt;&gt;P[i].y; vector&lt;Point&gt;H; H=ConvexHull(P); cout&lt;&lt;setprecision(9)&lt;&lt;perimeter(H)&lt;&lt;endl; //system("pause"); return 0; }; </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDrew Noakes
    1. USSerillan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COWhat are the characteristics of the sets of points for which your code produces (a) the right output and (b) the wrong output ? What have you learned from your own efforts to diagnose the root cause of the problem ?
      singulars
      1. POWhy isn't my convex hull perimeter calculation working?
      1. USHigh Performance Mark
    2. COActually it's going throught the online testing, so I don't see the inputs. I know that: number of points≥3 and 1 ≤ x, y ≤ 10^6. (x and y of every point)
      singulars
      1. POWhy isn't my convex hull perimeter calculation working?
      1. USSerillan
    3. COWhat is meant by "minimum perimeter of convex hull"? There's only one convex hull for a given set of points, and it only has one perimeter.
      singulars
      1. POWhy isn't my convex hull perimeter calculation working?
      1. USn.m.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload