Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. #define MAX_SIZE 1000
  7. const double PI = 2.0*acos(0.0);
  8. const double EPS = 1e-9; //too small/big?????
  9. struct PT
  10. {
  11.     double x,y;
  12.     double length() {return sqrt(x*x+y*y);}
  13.     int normalize()
  14. // normalize the vector to unit length; return -1 if the vector is 0
  15.     {
  16.         double l = length();
  17.         if(fabs(l)<EPS) return -1;
  18.         x/=l; y/=l;
  19.         return 0;
  20.     }
  21.     PT operator-(PT a)
  22.     {
  23.         PT r;
  24.         r.x=x-a.x; r.y=y-a.y;
  25.         return r;
  26.     }
  27.     PT operator+(PT a)
  28.     {
  29.         PT r;
  30.         r.x=x+a.x; r.y=y+a.y;
  31.         return r;
  32.     }
  33.     PT operator*(double sc)
  34.     {
  35.         PT r;
  36.         r.x=x*sc; r.y=y*sc;
  37.         return r;
  38.     }
  39. };
  40. bool operator<(const PT& a,const PT& b)
  41. {
  42.     if(fabs(a.x-b.x)<EPS) return a.y<b.y;
  43.     return a.x<b.x;
  44. }
  45. double dist(PT& a, PT& b)
  46. // the distance between two points
  47. {
  48.     return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
  49. }
  50. double dot(PT& a, PT& b)
  51. // the inner product of two vectors
  52. {
  53.     return(a.x*b.x+a.y*b.y);
  54. }
  55. // =================================================================
  56. // The Convex Hull
  57. // =================================================================
  58. int sideSign(PT& p1,PT& p2,PT& p3)
  59. // which side is p3 to the line p1->p2? returns: 1 left, 0 on, -1 right
  60. {
  61.     double sg = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y - p3.y)*(p2.x-p3.x);
  62.     if(fabs(sg)<EPS) return 0;
  63.     if(sg>0)return 1;
  64.     return -1;
  65. }
  66. bool better(PT& p1,PT& p2,PT& p3)
  67. // used by convec hull: from p3, if p1 is better than p2
  68. {
  69.     double sg = (p1.y - p3.y)*(p2.x-p3.x)-(p1.x-p3.x)*(p2.y-p3.y);
  70. //watch range of the numbers
  71.     if(fabs(sg)<EPS)
  72.     {
  73.         if(dist(p3,p1)>dist(p3,p2))return true;
  74.         else return false;
  75.     }
  76.     if(sg<0) return true;
  77.     return false;
  78. }
  79. //convex hull in n*n
  80. void vex(vector<PT>& vin,vector<PT>& vout)
  81. {
  82.     vout.clear();
  83.     int n=vin.size();
  84.     int st=0;
  85.     int i;
  86.     for(i=1;i<n;i++) if(vin[i]<vin[st]) st=i;
  87.         vector<int> used;
  88. // used[i] is the index of the i-th point on the hull
  89.     used.push_back(st);
  90.     int idx=st; int next;
  91.     do{
  92.         next=0;
  93.         for(i=1;i<n;i++)
  94.             if(better(vin[i],vin[next],vin[idx]))next=i;
  95.         idx=next;
  96.         used.push_back(idx);
  97.     }while(idx!=st);
  98.     for(i=0;i+1<used.size();i++) vout.push_back(vin[used[i]]);
  99. }
  100. //convex hull nlogn
  101. void vex2(vector<PT> vin,vector<PT>& vout)
  102. // vin is not pass by reference, since we will rotate it
  103. {
  104.     vout.clear();
  105.     int n=vin.size();
  106.     sort(vin.begin(),vin.end());
  107.     PT stk[MAX_SIZE];
  108.     int pstk, i;
  109. // hopefully more than 2 points
  110.     stk[0] = vin[0];
  111.     stk[1] = vin[1];
  112.     pstk = 2;
  113.     for(i=2; i<n; i++)
  114.     {
  115.         if(dist(vin[i], vin[i-1])<EPS) continue;
  116.         while(pstk > 1 && better(vin[i], stk[pstk-1], stk[pstk-2]))
  117.             pstk--;
  118.         stk[pstk] = vin[i];
  119.         pstk++;
  120.     }
  121.     for(i=0; i<pstk; i++) vout.push_back(stk[i]);
  122. // turn 180 degree
  123.         for(i=0; i<n; i++)
  124.         {
  125.             vin[i].y = -vin[i].y;
  126.             vin[i].x = -vin[i].x;
  127.         }
  128.         sort(vin.begin(), vin.end());
  129.         stk[0] = vin[0];
  130.         stk[1] = vin[1];
  131.         pstk = 2;
  132.         for(i=2; i<n; i++)
  133.         {
  134.             if(dist(vin[i], vin[i-1])<EPS) continue;
  135.             while(pstk > 1 && better(vin[i], stk[pstk-1], stk[pstk-2]))
  136.                 pstk--;
  137.             stk[pstk] = vin[i];
  138.             pstk++;
  139.         }
  140.         for(i=1; i<pstk-1; i++)
  141.         {
  142. stk[i].x= -stk[i].x; // don’t forget rotate 180 d back.
  143. stk[i].y= -stk[i].y;
  144. vout.push_back(stk[i]);
  145. }
  146. }
  147. int isConvex(vector<PT>& v)
  148. // test whether a simple polygon is convex
  149. // return 0 if not convex, 1 if strictly convex,
  150. // 2 if convex but there are points unnecesary
  151. // this function does not work if the polycon is self intersecting
  152. // in that case, compute the convex hull of v, and see if both have the same area
  153. {
  154.     int i,j,k;
  155.     int c1=0; int c2=0; int c0=0;
  156.     int n=v.size();
  157.     for(i=0;i<n;i++)
  158.     {
  159.         j=(i+1)%n;
  160.         k=(j+1)%n;
  161.         int s=sideSign(v[i], v[j], v[k]);
  162.         if(s==0) c0++;
  163.         if(s>0) c1++;
  164.         if(s<0) c2++;
  165.     }
  166.     if(c1 && c2) return 0;
  167.     if(c0) return 2;
  168.     return 1;
  169. }
  170. // ===============================================================
  171. // Areas
  172. // ===============================================================
  173. double trap(PT a, PT b)
  174. {
  175.     return (0.5*(b.x - a.x)*(b.y + a.y));
  176. }
  177. double area(vector<PT> &vin)
  178. // Area of a simple polygon, not neccessary convex
  179. {
  180.     int n = vin.size();
  181.     double ret = 0.0;
  182.     for(int i = 0; i < n; i++)
  183.         ret += trap(vin[i], vin[(i+1)%n]);
  184.     return fabs(ret);
  185. }
  186. double peri(vector<PT> &vin)
  187. // Perimeter of a simple polygon, not neccessary convex
  188. {
  189.     int n = vin.size();
  190.     double ret = 0.0;
  191.     for(int i = 0; i < n; i++)
  192.         ret += dist(vin[i], vin[(i+1)%n]);
  193.     return ret;
  194. }
  195. double triarea(PT a, PT b, PT c)
  196. {
  197.     return fabs(trap(a,b)+trap(b,c)+trap(c,a));
  198. }
  199. double height(PT a, PT b, PT c)
  200. // height from a to the line bc
  201. {
  202.     double s3 = dist(c, b);
  203.     double ar=triarea(a,b,c);
  204.     return(2.0*ar/s3);
  205. }
  206. // ====================================================
  207. // Points and Lines
  208. // ====================================================
  209. int intersection( PT p1, PT p2, PT p3, PT p4, PT &r )
  210. // two lines given by p1->p2, p3->p4 r is the intersection point
  211. // return -1 if two lines are parallel
  212. {
  213.     double d = (p4.y - p3.y)*(p2.x-p1.x) - (p4.x - p3.x)*(p2.y - p1.y);
  214.     if( fabs( d ) < EPS ) return -1;
  215. // might need to do something special!!!
  216.     double ua, ub;
  217.     ua = (p4.x - p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x);
  218.     ua /= d;
  219. // ub = (p2.x - p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x);
  220. //ub /= d;
  221.     r = p1 + (p2-p1)*ua;
  222.     return 0;
  223. }
  224. int pAndSeg(PT& p1, PT& p2, PT& p)
  225. // the relation of the point p and the segment p1->p2.
  226. // 1 if point is on the segment; 0 if not on the line; -1 if on the line but not on the segment
  227. {
  228.     double s=triarea(p, p1, p2);
  229.     if(s>EPS) return(0);
  230.     double sg=(p.x-p1.x)*(p.x-p2.x);
  231.     if(sg>EPS) return(-1);
  232.     sg=(p.y-p1.y)*(p.y-p2.y);
  233.     if(sg>EPS) return(-1);
  234.     return(1);
  235. }
  236. void closestpt( PT p1, PT p2, PT p3, PT &r )
  237. // the closest point on the segment p1->p2 to p3
  238. {
  239.     if( pAndSeg(p1,p2,p3) == 1)
  240.         { r = p3; return; }
  241.     PT v = p2-p1;
  242.     v.normalize();
  243.     double pr; // inner product
  244.     pr = (p3.y-p1.y)*v.y + (p3.x-p1.x)*v.x;
  245.     r = p1+v*pr;
  246.     if(pAndSeg(p1,p2,r)==-1){
  247.         if(dist(p3,p1)<dist(p3,p2))r=p1;
  248.         else r=p2;
  249.     }
  250. }
  251. // ===============================================
  252. // Angles
  253. // ===============================================
  254. void rotate(PT p0, PT p1, double a, PT& r)
  255. // rotate p1 around p0 clockwise, by angle a
  256. // don’t pass by reference for p1, so r and p1 can be the same
  257. {
  258.     p1 = p1-p0;
  259.     r.x = cos(a)*p1.x-sin(a)*p1.y;
  260.     r.y = sin(a)*p1.x+cos(a)*p1.y;
  261.     r = r+p0;
  262. }
  263. // ===============================================
  264. // points, lines, and circles
  265. // ===============================================
  266.  
  267. int pAndPoly(vector<PT> pv, PT p)
  268. // the relation of the point and the simple polygon
  269. // 1 if p is in pv; 0 outside; -1 on the polygon
  270. {
  271.     int i, j;
  272.     int n=pv.size();
  273.     pv.push_back(pv[0]);
  274.     for(i=0;i<n;i++)
  275.         if(pAndSeg(pv[i], pv[i+1], p)==1) return(-1);
  276.     for(i=0;i<n;i++)
  277.         pv[i] = pv[i]-p;
  278.     p.x=p.y=0.0;
  279.     double a, y;
  280.     while(1)
  281.     {
  282.         a=(double)rand()/10000.00;
  283.         j=0;
  284.         for(i=0;i<n;i++)
  285.         {
  286.             rotate(p, pv[i], a, pv[i]);
  287.             if(fabs(pv[i].x)<EPS) j=1;
  288.         }
  289.         if(j==0)
  290.         {
  291.             pv[n]=pv[0];
  292.             j=0;
  293.             for(i=0;i<n;i++) if(pv[i].x*pv[i+1].x < -EPS)
  294.             {
  295.                 y=pv[i+1].y-pv[i+1].x*(pv[i].y-pv[i+1].y)/(pv[i].x-pv[i+1].x);
  296.                 if(y>0) j++;
  297.             }
  298.             return(j%2);
  299.         }
  300.     }
  301.     return 1;
  302. }
  303. ostream& operator<<(ostream& o, const PT& p) {
  304.     return o << "(" << p.x << ", " << p.y << ")";
  305. }
  306. // ===================================================================
  307. // UVA 137, the intersection of two CONVEX polygons.
  308. // ===================================================================
  309. // return 1 if the intersection is empty.
  310. int PInterP(vector<PT>& p1, vector<PT>& p2, vector<PT>& p3)
  311. {
  312.     vector<PT> pts;
  313.     PT pp;
  314.     pts.clear();
  315.     int m=p1.size();
  316.     int n=p2.size();
  317.     int i, j;
  318.     for(i=0;i<m;i++)
  319.         if(pAndPoly(p2, p1[i])!=0) pts.push_back(p1[i]);
  320.     for(i=0;i<n;i++)
  321.         if(pAndPoly(p1, p2[i])!=0) pts.push_back(p2[i]);
  322.     if(m>1 && n>1)
  323.         for(i=0;i<m;i++)
  324.             for(j=0;j<n;j++)
  325.                 if(intersection(p1[i], p1[(i+1)%m], p2[j], p2[(j+1)%n], pp)==0)
  326.                 {
  327. //cout<<i<<" "<<j<<" -> "<<pp.x<<" "<<pp.y<<endl;
  328.                     if(pAndSeg(p1[i], p1[(i+1)%m], pp)!=1) continue;
  329.                     if(pAndSeg(p2[j], p2[(j+1)%n], pp)!=1) continue;
  330.                     pts.push_back(pp);
  331.                 }
  332.                 if(pts.size()<=1)
  333.                 {
  334.                     p3.resize(1);
  335.                     p3[0].x=p3[0].y=0.0;
  336.                     return(1);
  337.                 }
  338. //show(pts);
  339. vex2(pts, p3); // or vex
  340. return(0);
  341. }
  342. int main(){
  343.     ios_base::sync_with_stdio(false);
  344.     cin.tie(NULL);
  345.     int N;cin>>N;
  346.     while(N!=-1){
  347.         vector<vector<PT>> pts;
  348.         double A=0;
  349.         for(int i = 0;i<N;i++){
  350.             long I,D,H;
  351.             PT pt1,pt2,pt3;
  352.             vector<PT> temp;
  353.             cin>>I>>D>>H;
  354.             double mid = (I+D)*0.5;
  355.             pt1.x=I;pt1.y=0;temp.push_back(pt1);
  356.             pt2.x=D;pt2.y=0;temp.push_back(pt2);
  357.             pt3.x=mid;pt3.y=H;temp.push_back(pt3);
  358.             pts.push_back(temp);
  359.             A+=area(temp);
  360.             for(int j = 0; j < i; j++){
  361.                 vector<PT> temp1;
  362.                 if(PInterP(pts[j],temp,temp1)==0){
  363.                     A-=area(temp1);
  364.                 }
  365.             }
  366.         }
  367.         cout.precision(2);cout << fixed;
  368.         cout<<A<<"\n";
  369.         cin>>N;
  370.     }
  371. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement