Sgu/129

先极角排出凸多边形，然后对线段算出和多边形的交点（最多4个,交于两个角的时候是4个），去重后分类输出。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define dis(a, b) sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))
#define cross(a, b, c) ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)) 
struct point { 
       double x, y;
       bool operator < (const point &c) const { return (x < c.x || x == c.x && y < c.y); }
       bool operator == (const point &c) const { return (x == c.x && y == c.y); }  
};
int n, m;
point P[400], a, b, Q[5], q;
bool online;
 
bool cmp(const point &a, const point &b)
{
     return (cross(P[0], a, b) > 0);
}
 
bool intersect(const point &a, const point &b, const point &c, const point &d)
{
     double va = cross(c, d, a), vb = cross(c, d, b), 
            vc = cross(a, b, c), vd = cross(a, b, d);
     if (!va && !vb) { online = true; return false; }
     if (va * vb <= 0 && vc * vd <= 0)
     {
        vb = -vb;
        q.x = (a.x * vb + b.x * va) / (va + vb);
        q.y = (a.y * vb + b.y * va) / (va + vb);
        return true;
     }
     return false;
}
 
int main()
{
    scanf("%d", &n);
    m = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%lf %lf", &P[i].x, &P[i].y);
        if (P[i].y < P[m].y || P[i].y == P[m].y && P[i].x < P[m].x) m = i;
    }
    swap(P[0], P[m]);
    sort(P + 1, P + n, cmp);
 
    scanf("%d", &m);
    while (m--)
    {
          scanf("%lf %lf %lf %lf", &a.x, &a.y, &b.x, &b.y);
          bool ia = true, ib = true;
          int cnt = 0;
          online = false;
          for (int i = 0; i < n; ++i)
          {
              if (ia && cross(P[i], P[(i+1)%n], a) <= 0) ia = false;
              if (ib && cross(P[i], P[(i+1)%n], b) <= 0) ib = false;
              if (intersect(a, b, P[i], P[(i+1)%n])) Q[cnt++] = q;
              if (online) { ia = ib = cnt = 0; break; }
          }
          sort(Q, Q + cnt);
          cnt = unique(Q, Q + cnt) - Q;
          if (ia && ib) printf("%.2lf\n", dis(a, b)); else
          if (ia) printf("%.2lf\n", dis(a, Q[0])); else
          if (ib) printf("%.2lf\n", dis(b, Q[0])); else
          if (cnt == 2) printf("%.2lf\n", dis(Q[0], Q[1])); else
          printf("0.00\n");
    }
    return 0;
}
// From FingerSed