C++11(clang++ 3.9) 解法, 执行用时: 204ms, 内存消耗: 16208K, 提交时间: 2020-05-30 21:03:37

#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
//{{{ read()
inline ll read(){
	register ll x=0,f=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')	x=x*10+(ch^48),ch=getchar();
	return x*f;
}
//}}}
const int N=2e5+5;
int t,n,nd,cnt,ans=1,d[N];
struct each{
	int x1,y1,x2,y2,id;
	bool operator < (const each k) const{
		return 1.0*(y2-y1)/(x2-x1)*(t-x1)+y1<1.0*(k.y2-k.y1)/(k.x2-k.x1)*(t-k.x1)+k.y1;
	}
}a[N];
struct ins{
	int id,ty;
	ins(int dd=0,int yy=0){
		id=dd,ty=yy;
	}
};
set<each>se;
vector<ins>b[N];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		a[i].x1=read(),a[i].y1=read();
		a[i].x2=read(),a[i].y2=read();
		d[++cnt]=a[i].x1,d[++cnt]=a[i].x2,a[i].id=i;
	}
	sort(d+1,d+cnt+1);
	cnt=unique(d+1,d+cnt+1)-d-1;
	for(int i=1;i<=n;i++){
		int k=lower_bound(d+1,d+cnt+1,a[i].x1)-d;
		b[k].push_back(ins(i,1));
		k=lower_bound(d+1,d+cnt+1,a[i].x2)-d;
		b[k].push_back(ins(i,-1));
	}
	nd=1;
	for(int i=1;i<=cnt;i++){
		t=d[i];
		for(ins i:b[i]){
			if(a[nd]<a[i.id]||i.id==nd)	continue;
			if(i.ty==1)	se.insert(a[i.id]);
			else	se.erase(a[i.id]);
		}
		int k=lower_bound(d+1,d+cnt+1,a[nd].x2)-d;
		if(k==i){
			if(se.empty()){
				printf("%d\n",ans);
				return 0;
			}
			set<each>::iterator it=se.end();
			--it,nd=it->id,++ans;
			se.erase(it);
		}
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 107ms, 内存消耗: 11752K, 提交时间: 2020-07-05 17:10:37

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct Line
{
    static double x;
    double k, b;
    int id;
    friend bool operator<(const Line u, const Line v)
    {
        return (u.k * x + u.b) > (v.k * x + v.b);
    }
};

struct Mo
{
    int x, id, isbegin;
};

int n, i, X1[N], Y1[N], X2[N], Y2[N], q, now, ans = 1;
double Line::x;
Mo tmp;
Line ln[N];
deque<Mo> Q;
set<Line> S;

main()
{
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d%d%d%d", &X1[i], &Y1[i], &X2[i], &Y2[i]);
        Q.push_back({X1[i], i, 1});
        Q.push_back({X2[i], i, 0});
        ln[i].k = (Y1[i] - Y2[i]) / (double)(X1[i] - X2[i]);
        ln[i].b = Y1[i] - ln[i].k * X1[i];
        ln[i].id = i;
    }
    sort(Q.begin(), Q.end(), [](const Mo u, const Mo v) { return u.x < v.x; });
    now = 1;
    q = -1;
Start:
    while (Q.size() > 0 && (tmp = Q.front()).x <= X2[now])
    {
        Line::x = tmp.x;
        if (tmp.isbegin)
            S.insert(ln[tmp.id]);
        else
            S.erase(ln[tmp.id]);
        Q.pop_front();
    }
    Line::x = X2[now];
    auto tmp = S.lower_bound({0, (double)Y2[now], 0});
    if (tmp == S.end())
        goto End;
    now = tmp->id;
    ++ans;
    goto Start;
End:
    printf("%d", ans);
}