Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Dai Ca Di Hoc
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define reset(x) memset(x, 0,sizeof(x))
- #define Rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
- #define For(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
- #define MIN(x,y) if (x > (y)) x = (y)
- #define MAX(x,y) if (x < (y)) x = (y)
- #define PB push_back
- #define mp make_pair
- #define F first
- #define S second
- #define maxn 100005
- #define MOD 1000000007
- #define remain(x) if (x > MOD) x -= MOD
- #define pii pair<int, int>
- #define ll long long
- #define Task "dragon"
- using namespace std;
- struct Point{
- double X, Y;
- };
- vector <Point> a, b;
- int n;
- double d;
- struct Line{
- double AA, BB, CC;
- Line(){};
- Line(double A, double B, double C):AA(A), BB(B), CC(C){};
- Line(Point u, Point v){
- // a = y1-y2, b = x2 - x1, c = x1y2-x2y1
- double dx = v.X - u.X;
- double dy = v.Y - u.Y;
- AA = -dy; BB = dx; CC = u.X * v.Y - u.Y * v.X;
- }
- double Val(Point p)
- {
- return AA*p.X + BB*p.Y + CC;
- }
- };
- Line E[maxn];
- Point New[maxn];
- double Square(vector <Point> r){
- double sum = 0;
- //r.push_back(r[0]);
- for (int i = 1; i < r.size(); i++)
- sum += (r[i].X - r[i-1].X) * (r[i].Y + r[i-1].Y);
- return sum/2;
- }
- void Tinh(Line line, Point root, Point &A, Point &B){
- if (line.AA == 0){
- A = {root.X + d, root.Y};
- B = {root.X - d, root.Y};
- return;
- }
- double mau = line.BB * line.BB / line.AA / line.AA + 1;
- double dy = sqrt(d*d/mau);
- double dx = -dy*line.BB/line.AA;
- A = {root.X + dx, root.Y + dy};
- B = {root.X - dx, root.Y - dy};
- }
- void Resize_Polygon(){
- for (int i = 1; i <= n; i++){
- Line cur = Line(a[i], a[i-1]);
- double cc = cur.BB*a[i].X - cur.AA*a[i].Y;
- Line Cross = Line(-cur.BB, cur.AA, cc);
- Point A, B;
- Point O = a[i];
- Tinh(Cross, a[i], A, B);
- Point chose = i < n ? a[i+1] : a[i-2];
- if (cur.Val(chose) * cur.Val(A) > 0) A = B;
- E[i] = Line(cur.AA, cur.BB, -cur.AA * A.X - cur.BB * A.Y);
- }
- }
- Point Giao(Line p, Line q){
- if (p.AA == 0) swap(p,q);
- double yy = (q.AA * p.CC/p.AA - q.CC)/(q.BB - q.AA*p.BB/p.AA);
- double xx = -(p.BB*yy+p.CC)/p.AA;
- return {xx,yy};
- }
- void Cut(){
- E[0] = E[n];
- for (int i = 1; i <= n; i++) New[i] = Giao(E[i], E[i-1]);
- if (Square(a) < 0) for (int i = 1; i <= n/2; i++) swap(New[i], New[n-i+1]);
- for (int i = 1; i <= n; i++) New[i+n] = New[i];
- for (int i = 2; i <= n+1; i++)
- if (New[i-1].Y < 0 && New[i].Y > 0){
- Line Ox = Line(0,1,0);
- b.PB(Giao(Ox, Line(New[i], New[i-1])));
- while (New[i].Y > 0) b.PB(New[i++]);
- b.PB(Giao(Ox, Line(New[i], New[i-1])));
- b.PB(b[0]);
- return;
- }
- }
- int main()
- {
- //ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
- //freopen(Task".inp", "r", stdin);
- //freopen(Task".out", "w", stdout);
- cin >> n >> d;
- a.resize(n+1);
- for (int i = 0; i < n; i++) cin >> a[i].X >> a[i].Y;
- a[n] = a[0];
- Resize_Polygon();
- Cut();
- printf("%0.6f %0.6f", abs(Square(a)), abs(Square(b)));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement