Advertisement
Guest User

Untitled

a guest
Aug 19th, 2019
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 KB | None | 0 0
  1. //Dai Ca Di Hoc
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define reset(x) memset(x, 0,sizeof(x))
  5. #define Rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
  6. #define For(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
  7. #define MIN(x,y) if (x > (y)) x = (y)
  8. #define MAX(x,y) if (x < (y)) x = (y)
  9. #define PB push_back
  10. #define mp make_pair
  11. #define F first
  12. #define S second
  13. #define maxn 100005
  14. #define MOD 1000000007
  15. #define remain(x) if (x > MOD) x -= MOD
  16. #define pii pair<int, int>
  17. #define ll long long
  18. #define Task "dragon"
  19.  
  20. using namespace std;
  21.  
  22. struct Point{
  23.     double X, Y;
  24. };
  25. vector <Point> a, b;
  26. int n;
  27. double d;
  28.  
  29.  
  30.  
  31. struct Line{
  32.     double AA, BB, CC;
  33.     Line(){};
  34.     Line(double A, double B, double C):AA(A), BB(B), CC(C){};
  35.     Line(Point u, Point v){
  36.         // a = y1-y2, b = x2 - x1, c = x1y2-x2y1
  37.         double dx = v.X - u.X;
  38.         double dy = v.Y - u.Y;
  39.         AA = -dy; BB = dx; CC = u.X * v.Y - u.Y * v.X;
  40.     }
  41.     double Val(Point p)
  42.     {
  43.         return AA*p.X + BB*p.Y + CC;
  44.     }
  45. };
  46.  
  47. Line E[maxn];
  48. Point New[maxn];
  49.  
  50. double Square(vector <Point> r){
  51.     double sum = 0;
  52.     //r.push_back(r[0]);
  53.     for (int i = 1; i < r.size(); i++)
  54.         sum += (r[i].X - r[i-1].X) * (r[i].Y + r[i-1].Y);
  55.     return sum/2;
  56. }
  57.  
  58. void Tinh(Line line, Point root, Point &A, Point &B){
  59.     if (line.AA == 0){
  60.         A = {root.X + d, root.Y};
  61.         B = {root.X - d, root.Y};
  62.         return;
  63.     }
  64.     double mau = line.BB * line.BB / line.AA / line.AA + 1;
  65.     double dy = sqrt(d*d/mau);
  66.     double dx = -dy*line.BB/line.AA;
  67.     A = {root.X + dx, root.Y + dy};
  68.     B = {root.X - dx, root.Y - dy};
  69. }
  70.  
  71. void Resize_Polygon(){
  72.     for (int i = 1; i <= n; i++){
  73.         Line cur = Line(a[i], a[i-1]);
  74.         double cc = cur.BB*a[i].X - cur.AA*a[i].Y;
  75.         Line Cross = Line(-cur.BB, cur.AA, cc);
  76.         Point A, B;
  77.         Point O = a[i];
  78.         Tinh(Cross, a[i], A, B);
  79.         Point chose = i < n ? a[i+1] : a[i-2];
  80.         if (cur.Val(chose) * cur.Val(A) > 0) A = B;
  81.         E[i] = Line(cur.AA, cur.BB, -cur.AA * A.X - cur.BB * A.Y);
  82.     }
  83. }
  84.  
  85. Point Giao(Line p, Line q){
  86.     if (p.AA == 0) swap(p,q);
  87.     double yy = (q.AA * p.CC/p.AA - q.CC)/(q.BB - q.AA*p.BB/p.AA);
  88.     double xx = -(p.BB*yy+p.CC)/p.AA;
  89.     return {xx,yy};
  90. }
  91.  
  92. void Cut(){
  93.     E[0] = E[n];
  94.     for (int i = 1; i <= n; i++) New[i] = Giao(E[i], E[i-1]);
  95.     if (Square(a) < 0) for (int i = 1; i <= n/2; i++) swap(New[i], New[n-i+1]);
  96.     for (int i = 1; i <= n; i++) New[i+n] = New[i];
  97.     for (int i = 2; i <= n+1; i++)
  98.         if (New[i-1].Y < 0 && New[i].Y > 0){
  99.             Line Ox = Line(0,1,0);
  100.             b.PB(Giao(Ox, Line(New[i], New[i-1])));
  101.             while (New[i].Y > 0) b.PB(New[i++]);
  102.             b.PB(Giao(Ox, Line(New[i], New[i-1])));
  103.             b.PB(b[0]);
  104.             return;
  105.         }
  106. }
  107.  
  108. int main()
  109. {
  110.     //ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
  111.     //freopen(Task".inp", "r", stdin);
  112.     //freopen(Task".out", "w", stdout);
  113.     cin >> n >> d;
  114.     a.resize(n+1);
  115.     for (int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y;
  116.     a[n] = a[0];
  117.     Resize_Polygon();
  118.     Cut();
  119.     printf("%0.6f %0.6f", abs(Square(a)), abs(Square(b)));
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement