C++(g++ 7.5.0) 解法, 执行用时: 419ms, 内存消耗: 2592K, 提交时间: 2023-07-10 13:55:43
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include<vector>
#include<stdio.h>
#include<iomanip>
/*
有时候eps反而要调大
判断直线和线段有没有交点，直接看两个toleft即可，如果先求直线和线段交点，再判断交点在不在线段上，精度会出问题
尽量用toleft等bool去判断，而不是算出来某个点的坐标再去对比
最好不要求角度，精度有问题。
math.h要用fabs,cmath可以用abs但必须要using namespace
*/
using namespace std;
typedef double db;
const db eps = 1e-9;
int sign(db a) { return a < -eps ? -1 : a > eps; }
int cmp(db a, db b) { return sign(a - b); }
db min(db a,db b)
{
if(a<b)
return a;
return b;
}
//判断m是否介于a,b之间,不需要a<b
bool db_ismiddle(db a, db m, db b)
{
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
struct Point
{
db x, y;
Point(db x = 0, db y = 0) : x(x), y(y) {}
bool operator==(const Point &a) const { return (abs(x - a.x) <= eps && abs(y - a.y) <= eps); }
Point operator+(const Point &a) const { return {x + a.x, y + a.y}; }//okk
Point operator-(const Point &a) const { return {x - a.x, y - a.y}; }//okk
Point operator-() const { return {-x, -y}; }
Point operator*(const db k) const { return {k * x, k * y}; }//okk
Point operator/(const db k) const { return {x / k, y / k}; }//okk
db operator*(const Point &a) const { return x * a.x + y * a.y; } // Dot okk
db operator^(const Point &a) const { return x * a.y - y * a.x; } // Cross okk
bool operator<(const Point &a) const
{
if (abs(x - a.x) <= eps)
return y < a.y - eps;
return x < a.x - eps;
}
//点是否介于点a,b之间，即在以a,b为对角线的矩形内，a,b可以交换顺序
bool ismiddle(const Point &a, const Point &b) const//okkk
{
return db_ismiddle(a.x, (*this).x, b.x) && db_ismiddle(a.y, (*this).y, b.y);
}
// 向量平行
bool is_par(const Point &a) const { return abs((*this) ^ a) <= eps; } //okk
// 向量垂直
bool is_ver(const Point &a) const { return abs((*this) * a) <= eps; }
// 判断向量a是否在这个向量的左侧
int toleft(const Point &a) const//okk
{
const auto t = (*this) ^ a;
return (t > eps) - (t < -eps);
}
//判断点不严格在线段上,在端点也算
int onseg(const Point &a,const Point &b){
return (b - a) ^ ((*this) - a) == 0 && ismiddle(a, b);
}
//单位向量
Point unit() const { return (*this) / len(); }//okk
// 逆时针转90度
Point rot90() const { return Point(-y, x); }
// 极角,[-pi,pi]
db alpha() { return atan2(y, x); }
// 向量模长平方
db len2() const { return (*this) * (*this); }
// 两点距离平方
db dis2(const Point &a) const { return (a - (*this)).len2(); }
// 向量模长
db len() const { return sqrt(len2()); }
// 两点距离
db dis(const Point &a) const { return (a - (*this)).len(); }
// 向量夹角
db ang(const Point &a) const { return acos(((*this) * a) / (this->len() * a.len())); }
//看向量是否在x轴上方，极角在[0,pi)属于上面，[-pi,0)属于下面
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); } //okkkk
//点到直线ab的投影点，a!=b
Point proj(const Point &a, const Point &b)const
{
Point dir = b - a;
return a + dir * (dir * ((*this) - a) / dir.len2());
}
//关于直线ab的对称点
Point sym(const Point &a,const Point &b)const
{
return (*this).proj(a, b) * 2 - (*this);
}
//点到线段的最短距离
db dis_to_seg(const Point &a, const Point &b)
{
if (a == b)
return (*this).dis(a);
Point h = (*this).proj(a, b);
if ((*this).ismiddle(a, b))
return (*this).dis(h);
return min((*this).dis(a), (*this).dis(b));
}
// 向量逆时针旋转rad
Point rot(const double rad) const { return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)}; }
void write() { std::cout << "(" << x << "," << y << ")" << '\n'; }
};
//按o1点极角排序
// sort(p.begin(), p.end(), [&](const P &a, const P &b){
// int qa = (a-o1).quad(), qb = (b-o1).quad();
// if(qa!=qb)
// return qa < qb;
// else
// return sign((a-o1) ^ (b-o1)) > 0;
// });
struct Line
{
Point p, v; // p+tv
Line(Point a, Point b) : p(a), v(b) {}
bool operator==(const Line &a) const { return (v.is_par(a.v) && v.is_par(p - a.p)); }
// 两直线平行
bool is_par(const Line &a) const { return (v.is_par(a.v) && !v.is_par(p - a.p)); }
// 两直线垂直
bool is_ver(const Line &a) const { return v.is_ver(a.v); }
// 点a是否在直线上
bool is_on(const Point &a) const { return v.is_par(a - p); }
// 点a是否在直线左边
int toleft(const Point &a) const { return v.toleft(a - p); }
// 两直线交点，要提前排除平行情况
Point inter(const Line &a) const { return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v)); }
// 点a到直线距离
db dis(const Point &a) const { return abs(v ^ (a - p)) / v.len(); }
// 点a到直线投影
Point proj(const Point &a) const { return p + v * ((v * (a - p)) / (v * v)); }
//判断直线和线段有没有交点，重合，交在端点也算
bool isinter_on_seg(const Point &a,const Point &b)const{
return (*this).toleft(a) * (*this).toleft(b) <= 0;
// 去掉=就是交在线段内部
}
/*bool operator<(const Line &a) const
{
if (abs(v^a.v)<=eps && v*a.v>=-eps) return ((a.p-p)^v)>eps;
return argcmp(v,a.v);
}*/
};
struct Seg{
Point a, b;
Seg(Point _a,Point _b):a(_a),b(_b){}
//线段是否相交
bool is_inter_seg(Point c,Point d){
Line l1(a, b - a);
Line l2(c, d - c);
if (l1.isinter_on_seg(c, d) && l2.isinter_on_seg(a, b))
return 1;
return 0;
}
};
typedef Point P;
typedef Line L;
typedef P Vector;
typedef Seg S;
//多边形
//求简单多边形面积
db area(vector<Point>ps){//点按逆时针方向给，顺时针给的答案取个反就行
db ret = 0;
for (int i = 0; i < ps.size();++i)
ret += ps[i] ^ ps[(i + 1) % ps.size()];
return ret / 2;
}
db crossop(Point a,Point b,Point c){//okkkk
return sign((b - a) ^ (c - b));
}
//求凸包，自己选返回值，vector时逆时针返回下凸集，上凸集
//是严格凸包，求周长不影响，求点集有影响，abc三点共线不会把b算进去
//首先处理一下重合点
db convexHull(vector<Point>ps){//okkkkkk
int n = ps.size();
if(n<=1)
return 0;
// return ps;
sort(ps.begin(), ps.end());
vector<Point> qs(n * 2);
int k = 0;
for (int i = 0; i < n;qs[k++]=ps[i++])
while(k>1&&crossop(qs[k-2],qs[k-1],ps[i])<=0)
--k;
for (int i = n - 2, t = k; i >= 0;qs[k++]=ps[i--])
while(k>t&&crossop(qs[k-2],qs[k-1],ps[i])<=0)
--k;
qs.resize(k - 1);
db res = 0;
for (int i = 0; i < qs.size()-1;++i)
res += qs[i].dis(qs[i + 1]);
res += qs[qs.size() - 1].dis(qs[0]);
return res;
//return qs; // 如果返回点集，第一个点只存了一次
}
//旋转卡壳求凸多边形直径,ps要求逆时针
db convexDiameter(vector<Point> ps){//okkkkk
int n = ps.size();
if(n<=1)
return 0;
int is = 0, js = 0;
for (int k = 1; k < n;++k)
is = ps[k] < ps[is] ? k : is, js = ps[js] < ps[k] ? k : js;
int i = is, j = js;
db ret = ps[i].dis(ps[j]);
do{
if (((ps[(i + 1) % n] - ps[i]) ^ (ps[(j + 1) % n] - ps[j]))>=0)
(++j) %= n;
else
(++i) %= n;
ret = max(ret, ps[i].dis(ps[j]));
} while (i != is || j != js);
return ret;
}
//直线切凸多边形，返回直线左边的多边形,ps要求逆时针顺序,直线方向向量为q1q2
vector<P>convexCut(const vector<P> ps,P q1,P q2){
vector<P> qs;
int n = ps.size();
for (int i = 0; i < n;++i)
{
P p1 = ps[i], p2 = ps[(i + 1) % n];
int d1 = crossop(q1, q2, p1), d2 = crossop(q1, q2, p2);
if(d1>=0)
qs.push_back(p1);
if(d1*d2<0)
qs.push_back(L{p1, p1 - p2}.inter(L{q1, q1 - q2}));
}
return qs;
}
db calc(P a,P b,P c,vector<P>ps)
{
vector<P> qs;
qs = convexCut(ps, a, a + (b - a).rot90());
qs = convexCut(qs, a, a + (c - a).rot90());
return abs(area(qs));
}
void solve()
{
db xl, yl, xr, yr;
scanf("%lf%lf%lf%lf", &xl, &yl, &xr, &yr);
P p1, p2, p3, p4;
scanf("%lf%lf%lf%lf", &p1.x, &p1.y, &p2.x, &p2.y);
scanf("%lf%lf%lf%lf", &p3.x, &p3.y, &p4.x, &p4.y);
if(!S{p1,p2}.is_inter_seg(p3,p4))
{
printf("0.000000000000000\n");
return;
}
if((p1==p3&&p2==p4)||(p1==p4&&p2==p3))
{
printf("%.15lf\n", (xr - xl) * (yr - yl));
return;
}
vector<P> rect = {P(xl, yl), P(xr, yl), P(xr, yr), P(xl, yr)};
vector<P> p;
db ans = 0;
if(Vector{p1-p2}.is_par(p3-p4))
{
p = convexCut(rect, p1, p1 + (p1 - p2).rot90());
p = convexCut(p, p2, p2 + (p2 - p1).rot90());
p = convexCut(p, p3, p3 + (p3 - p4).rot90());
p = convexCut(p, p4, p4 + (p4 - p3).rot90());
ans+=area(p);
}
if(p1==p3)
ans += calc(p1, p2, p4, rect);
else if(p1==p4)
ans += calc(p1, p2, p3, rect);
else if(p2==p3)
ans += calc(p2, p1, p4, rect);
else if(p2==p4)
ans += calc(p2, p1, p3, rect);
printf("%.15lf\n", ans);
}
int main()
{
ios::sync_with_stdio(false);
int t;
scanf("%d", &t);
while(t--)
{
solve();
}
return 0;
}
/*
0 0 4 4
3 0 3 1
4 0 3 1
*/
C++ 解法, 执行用时: 417ms, 内存消耗: 2316K, 提交时间: 2022-05-01 20:17:44
#include <bits/stdc++.h>
#define fp(i,a,b) for(int i=a,__##i=(b)+1;i<__##i;++i)
#define fd(i,a,b) for(int i=a,__##i=(b)-1;i>__##i;--i)
#define X first
#define Y second
using namespace std;
const int N=1e5+5;
using arr=int[N];
using ll=long long;
using db=long double;
using pdd=pair<db,db>;
const db eps=1e-12;
inline void Read(pdd &p){ scanf("%Lf%Lf",&p.X,&p.Y); }
inline void Print(pdd &p){ cout<<p.X<<','<<p.Y<<' '; }
inline db Cross(const pdd &l,const pdd &r){ return l.X*r.Y-l.Y*r.X; }
inline pdd operator -(const pdd &l,const pdd &r){ return {l.X-r.X,l.Y-r.Y}; }
inline pdd operator +(const pdd &l,const pdd &r){ return {l.X+r.X,l.Y+r.Y}; }
inline pdd operator *(const db l,const pdd &r){ return {l*r.X,l*r.Y}; }
inline pdd Rot(const pdd p){ return {-p.Y,p.X}; }
inline bool Equal(const pdd &l,const pdd &r){ return abs(l.X-r.X)<eps&&abs(l.Y-r.Y)<eps; }
inline pdd Inter(pdd s1,pdd e1,pdd s2,pdd e2){
auto d=Cross(e1-s1,e2-s2);
if(abs(d)<eps) return pdd();
auto p=Cross(e1-s2,e2-s2),q=Cross(e2-s2,s1-s2);
return (1.0/d)*(p*s1+q*e1);
}
inline vector<pdd> Cut(const vector<pdd> &poly,pdd s,pdd e){
vector<pdd> ret;
fp(i,0,(int)poly.size()-1){
pdd cur=poly[i],prev=i?poly[i-1]:poly.back();
bool side=Cross(e-s,cur-s)<-eps;
if(side!=(Cross(e-s,prev-s)<-eps)) ret.push_back(Inter(s,e,cur,prev));
if(side) ret.push_back(cur);
}
return ret;
}
inline db Area(const vector<pdd> &poly){
db ret=0;
fp(i,0,(int)poly.size()-1){
pdd u=poly[i],v=i?poly[i-1]:poly.back();
ret+=Cross(v,u);
}
return ret/2;
}
int n;
inline db Solve(){
db xl,xr,yl,yr;
scanf("%Lf%Lf%Lf%Lf",&xl,&yl,&xr,&yr);
pdd P1(xl,yl),P2(xr,yl),P3(xr,yr),P4(xl,yr);
vector<pdd> P{P1,P2,P3,P4};
pdd A1,A2,B1,B2;
Read(A1), Read(A2), Read(B1), Read(B2);
if(A1>A2) swap(A1,A2);
if(B1>B2) swap(B1,B2);
if(Equal(A1,B1)&&Equal(A2,B2)){
auto sz=P3-P1;
return sz.X*sz.Y;
}
db ans=0;
if(abs(Cross(A2-A1,B2-A1))<eps&&abs(Cross(A2-A1,B1-A1))<eps){
pdd L=max(A1,B1),R=min(A2,B2);
if(L<R){
auto v=Cut(P,L,L+Rot(R-L));
v=Cut(v,R,R+Rot(L-R));
ans+=Area(v);
}
}
if(Equal(A1,B2)) swap(B1,B2);
else if(Equal(A2,B1)) swap(A1,A2);
else if(Equal(A2,B2)) swap(A1,A2),swap(B1,B2);
if(Equal(A1,B1)){
auto v=Cut(P,A1,A1+Rot(A1-A2));
v=Cut(v,B1,B1+Rot(B1-B2));
ans+=Area(v);
}
return ans;
}
int main() {
int T; scanf("%d",&T);
while(T--) printf("%.12Lf\n",Solve());
return 0;
}
%7D)
while the top-right corner is at coordinate %7D)
. There are two segments 
and 
lying strictly inside the rectangle. The two segments may share common points. There is also a car inside the rectangle, which can be regarded as a point.
and a segment 
is defined as the minimum Euclidean distance from 
), indicating the number of test cases.
, denoting the coordinates of the bottom-left and the top-right corners of the rectangle. Each of the next two lines contains four integers
, denoting a segment that connects
and
, where
and
.
.
.