Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- using namespace std;
- #define MAX_SIZE 1000
- const double PI = 2.0*acos(0.0);
- const double EPS = 1e-9; //too small/big?????
- struct PT
- {
- double x,y;
- double length() {return sqrt(x*x+y*y);}
- int normalize()
- // normalize the vector to unit length; return -1 if the vector is 0
- {
- double l = length();
- if(fabs(l)<EPS) return -1;
- x/=l; y/=l;
- return 0;
- }
- PT operator-(PT a)
- {
- PT r;
- r.x=x-a.x; r.y=y-a.y;
- return r;
- }
- PT operator+(PT a)
- {
- PT r;
- r.x=x+a.x; r.y=y+a.y;
- return r;
- }
- PT operator*(double sc)
- {
- PT r;
- r.x=x*sc; r.y=y*sc;
- return r;
- }
- };
- bool operator<(const PT& a,const PT& b)
- {
- if(fabs(a.x-b.x)<EPS) return a.y<b.y;
- return a.x<b.x;
- }
- double dist(PT& a, PT& b)
- // the distance between two points
- {
- return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
- }
- double dot(PT& a, PT& b)
- // the inner product of two vectors
- {
- return(a.x*b.x+a.y*b.y);
- }
- // =================================================================
- // The Convex Hull
- // =================================================================
- int sideSign(PT& p1,PT& p2,PT& p3)
- // which side is p3 to the line p1->p2? returns: 1 left, 0 on, -1 right
- {
- double sg = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y - p3.y)*(p2.x-p3.x);
- if(fabs(sg)<EPS) return 0;
- if(sg>0)return 1;
- return -1;
- }
- bool better(PT& p1,PT& p2,PT& p3)
- // used by convec hull: from p3, if p1 is better than p2
- {
- double sg = (p1.y - p3.y)*(p2.x-p3.x)-(p1.x-p3.x)*(p2.y-p3.y);
- //watch range of the numbers
- if(fabs(sg)<EPS)
- {
- if(dist(p3,p1)>dist(p3,p2))return true;
- else return false;
- }
- if(sg<0) return true;
- return false;
- }
- //convex hull in n*n
- void vex(vector<PT>& vin,vector<PT>& vout)
- {
- vout.clear();
- int n=vin.size();
- int st=0;
- int i;
- for(i=1;i<n;i++) if(vin[i]<vin[st]) st=i;
- vector<int> used;
- // used[i] is the index of the i-th point on the hull
- used.push_back(st);
- int idx=st; int next;
- do{
- next=0;
- for(i=1;i<n;i++)
- if(better(vin[i],vin[next],vin[idx]))next=i;
- idx=next;
- used.push_back(idx);
- }while(idx!=st);
- for(i=0;i+1<used.size();i++) vout.push_back(vin[used[i]]);
- }
- //convex hull nlogn
- void vex2(vector<PT> vin,vector<PT>& vout)
- // vin is not pass by reference, since we will rotate it
- {
- vout.clear();
- int n=vin.size();
- sort(vin.begin(),vin.end());
- PT stk[MAX_SIZE];
- int pstk, i;
- // hopefully more than 2 points
- stk[0] = vin[0];
- stk[1] = vin[1];
- pstk = 2;
- for(i=2; i<n; i++)
- {
- if(dist(vin[i], vin[i-1])<EPS) continue;
- while(pstk > 1 && better(vin[i], stk[pstk-1], stk[pstk-2]))
- pstk--;
- stk[pstk] = vin[i];
- pstk++;
- }
- for(i=0; i<pstk; i++) vout.push_back(stk[i]);
- // turn 180 degree
- for(i=0; i<n; i++)
- {
- vin[i].y = -vin[i].y;
- vin[i].x = -vin[i].x;
- }
- sort(vin.begin(), vin.end());
- stk[0] = vin[0];
- stk[1] = vin[1];
- pstk = 2;
- for(i=2; i<n; i++)
- {
- if(dist(vin[i], vin[i-1])<EPS) continue;
- while(pstk > 1 && better(vin[i], stk[pstk-1], stk[pstk-2]))
- pstk--;
- stk[pstk] = vin[i];
- pstk++;
- }
- for(i=1; i<pstk-1; i++)
- {
- stk[i].x= -stk[i].x; // don’t forget rotate 180 d back.
- stk[i].y= -stk[i].y;
- vout.push_back(stk[i]);
- }
- }
- int isConvex(vector<PT>& v)
- // test whether a simple polygon is convex
- // return 0 if not convex, 1 if strictly convex,
- // 2 if convex but there are points unnecesary
- // this function does not work if the polycon is self intersecting
- // in that case, compute the convex hull of v, and see if both have the same area
- {
- int i,j,k;
- int c1=0; int c2=0; int c0=0;
- int n=v.size();
- for(i=0;i<n;i++)
- {
- j=(i+1)%n;
- k=(j+1)%n;
- int s=sideSign(v[i], v[j], v[k]);
- if(s==0) c0++;
- if(s>0) c1++;
- if(s<0) c2++;
- }
- if(c1 && c2) return 0;
- if(c0) return 2;
- return 1;
- }
- // ===============================================================
- // Areas
- // ===============================================================
- double trap(PT a, PT b)
- {
- return (0.5*(b.x - a.x)*(b.y + a.y));
- }
- double area(vector<PT> &vin)
- // Area of a simple polygon, not neccessary convex
- {
- int n = vin.size();
- double ret = 0.0;
- for(int i = 0; i < n; i++)
- ret += trap(vin[i], vin[(i+1)%n]);
- return fabs(ret);
- }
- double peri(vector<PT> &vin)
- // Perimeter of a simple polygon, not neccessary convex
- {
- int n = vin.size();
- double ret = 0.0;
- for(int i = 0; i < n; i++)
- ret += dist(vin[i], vin[(i+1)%n]);
- return ret;
- }
- double triarea(PT a, PT b, PT c)
- {
- return fabs(trap(a,b)+trap(b,c)+trap(c,a));
- }
- double height(PT a, PT b, PT c)
- // height from a to the line bc
- {
- double s3 = dist(c, b);
- double ar=triarea(a,b,c);
- return(2.0*ar/s3);
- }
- // ====================================================
- // Points and Lines
- // ====================================================
- int intersection( PT p1, PT p2, PT p3, PT p4, PT &r )
- // two lines given by p1->p2, p3->p4 r is the intersection point
- // return -1 if two lines are parallel
- {
- double d = (p4.y - p3.y)*(p2.x-p1.x) - (p4.x - p3.x)*(p2.y - p1.y);
- if( fabs( d ) < EPS ) return -1;
- // might need to do something special!!!
- double ua, ub;
- ua = (p4.x - p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x);
- ua /= d;
- // ub = (p2.x - p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x);
- //ub /= d;
- r = p1 + (p2-p1)*ua;
- return 0;
- }
- int pAndSeg(PT& p1, PT& p2, PT& p)
- // the relation of the point p and the segment p1->p2.
- // 1 if point is on the segment; 0 if not on the line; -1 if on the line but not on the segment
- {
- double s=triarea(p, p1, p2);
- if(s>EPS) return(0);
- double sg=(p.x-p1.x)*(p.x-p2.x);
- if(sg>EPS) return(-1);
- sg=(p.y-p1.y)*(p.y-p2.y);
- if(sg>EPS) return(-1);
- return(1);
- }
- void closestpt( PT p1, PT p2, PT p3, PT &r )
- // the closest point on the segment p1->p2 to p3
- {
- if( pAndSeg(p1,p2,p3) == 1)
- { r = p3; return; }
- PT v = p2-p1;
- v.normalize();
- double pr; // inner product
- pr = (p3.y-p1.y)*v.y + (p3.x-p1.x)*v.x;
- r = p1+v*pr;
- if(pAndSeg(p1,p2,r)==-1){
- if(dist(p3,p1)<dist(p3,p2))r=p1;
- else r=p2;
- }
- }
- // ===============================================
- // Angles
- // ===============================================
- void rotate(PT p0, PT p1, double a, PT& r)
- // rotate p1 around p0 clockwise, by angle a
- // don’t pass by reference for p1, so r and p1 can be the same
- {
- p1 = p1-p0;
- r.x = cos(a)*p1.x-sin(a)*p1.y;
- r.y = sin(a)*p1.x+cos(a)*p1.y;
- r = r+p0;
- }
- // ===============================================
- // points, lines, and circles
- // ===============================================
- int pAndPoly(vector<PT> pv, PT p)
- // the relation of the point and the simple polygon
- // 1 if p is in pv; 0 outside; -1 on the polygon
- {
- int i, j;
- int n=pv.size();
- pv.push_back(pv[0]);
- for(i=0;i<n;i++)
- if(pAndSeg(pv[i], pv[i+1], p)==1) return(-1);
- for(i=0;i<n;i++)
- pv[i] = pv[i]-p;
- p.x=p.y=0.0;
- double a, y;
- while(1)
- {
- a=(double)rand()/10000.00;
- j=0;
- for(i=0;i<n;i++)
- {
- rotate(p, pv[i], a, pv[i]);
- if(fabs(pv[i].x)<EPS) j=1;
- }
- if(j==0)
- {
- pv[n]=pv[0];
- j=0;
- for(i=0;i<n;i++) if(pv[i].x*pv[i+1].x < -EPS)
- {
- y=pv[i+1].y-pv[i+1].x*(pv[i].y-pv[i+1].y)/(pv[i].x-pv[i+1].x);
- if(y>0) j++;
- }
- return(j%2);
- }
- }
- return 1;
- }
- ostream& operator<<(ostream& o, const PT& p) {
- return o << "(" << p.x << ", " << p.y << ")";
- }
- // ===================================================================
- // UVA 137, the intersection of two CONVEX polygons.
- // ===================================================================
- // return 1 if the intersection is empty.
- int PInterP(vector<PT>& p1, vector<PT>& p2, vector<PT>& p3)
- {
- vector<PT> pts;
- PT pp;
- pts.clear();
- int m=p1.size();
- int n=p2.size();
- int i, j;
- for(i=0;i<m;i++)
- if(pAndPoly(p2, p1[i])!=0) pts.push_back(p1[i]);
- for(i=0;i<n;i++)
- if(pAndPoly(p1, p2[i])!=0) pts.push_back(p2[i]);
- if(m>1 && n>1)
- for(i=0;i<m;i++)
- for(j=0;j<n;j++)
- if(intersection(p1[i], p1[(i+1)%m], p2[j], p2[(j+1)%n], pp)==0)
- {
- //cout<<i<<" "<<j<<" -> "<<pp.x<<" "<<pp.y<<endl;
- if(pAndSeg(p1[i], p1[(i+1)%m], pp)!=1) continue;
- if(pAndSeg(p2[j], p2[(j+1)%n], pp)!=1) continue;
- pts.push_back(pp);
- }
- if(pts.size()<=1)
- {
- p3.resize(1);
- p3[0].x=p3[0].y=0.0;
- return(1);
- }
- //show(pts);
- vex2(pts, p3); // or vex
- return(0);
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N;cin>>N;
- while(N!=-1){
- vector<vector<PT>> pts;
- double A=0;
- for(int i = 0;i<N;i++){
- long I,D,H;
- PT pt1,pt2,pt3;
- vector<PT> temp;
- cin>>I>>D>>H;
- double mid = (I+D)*0.5;
- pt1.x=I;pt1.y=0;temp.push_back(pt1);
- pt2.x=D;pt2.y=0;temp.push_back(pt2);
- pt3.x=mid;pt3.y=H;temp.push_back(pt3);
- pts.push_back(temp);
- A+=area(temp);
- for(int j = 0; j < i; j++){
- vector<PT> temp1;
- if(PInterP(pts[j],temp,temp1)==0){
- A-=area(temp1);
- }
- }
- }
- cout.precision(2);cout << fixed;
- cout<<A<<"\n";
- cin>>N;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement