ural1469

宣毅鸣 宣毅鸣     2022-10-03     418

关键词:

题解:

从左往右加入每一个点

判断一下和,pre,nxt是否相交

删除得时候也要判断

代码:

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=200010;
typedef double ld;
const ld eps=1e-8,C=0.18479956785822313167427314019291;
struct nd{int id,ls,rs,rk,fa;ld key;}t[N];
struct se{ld x1,y1,x2,y2,k,b;}s[N];
struct Tp{ld sg,x;int id;}p[N];
int n,m,rt,date[N];
int cmp(const Tp &a,const Tp &b){return (a.x<b.x);}
void rotate(ld &x,ld &y)
{
    ld p=x,q=y;
    x=cos(C)*p-sin(C)*q;
    y=sin(C)*p+cos(C)*q;
}
int zig(int d)
{
    int tmp=t[d].ls;
    t[d].ls=t[tmp].rs;t[tmp].rs=d;
    t[tmp].fa=t[d].fa;
    t[d].fa=tmp;
    if (t[d].ls) t[t[d].ls].fa=d;
    return tmp;
}
int zag(int d)
{
    int tmp=t[d].rs;
    t[d].rs=t[tmp].ls;t[tmp].ls=d;
    t[tmp].fa=t[d].fa;
    t[d].fa=tmp;
    if (t[d].rs) t[t[d].rs].fa=d;
    return tmp;
}
int ins(int d,ld y,ld x,int id)
{
    if (!d)
      {
        date[id]=++m;
        t[m].key=y;t[m].id=id;
        t[m].fa=0;t[m].rk=rand();
        return m;
     }
    ld _y=s[t[d].id].k*x+s[t[d].id].b;
    if (fabs(y-_y)<=eps)
     {
        printf("YES
%d %d
",id+1,t[d].id+1);
        exit(0);
     }
    if (y<_y)
     {
        t[d].ls=ins(t[d].ls,y,x,id);
        t[t[d].ls].fa=d;
        if (t[t[d].ls].rk<t[d].rk)return zig(d);
        else return d;
     }
    t[d].rs=ins(t[d].rs,y,x,id);
    t[t[d].rs].fa=d;
    if (t[t[d].rs].rk<t[d].rk)return zag(d);
    else return d;
}
int del(int d,ld y,ld x)
{
    ld _y=s[t[d].id].k*x+s[t[d].id].b;
    if (fabs(y-_y)<=eps)
     {
        if (!(t[d].ls+t[d].rs)) return 0;
        if ((t[d].ls)&&((!t[d].rs)||(t[t[d].ls].rk<t[t[d].rs].rk)))d=zig(d);
        else d=zag(d);
        return del(d,y,x);
     }
    if (y<_y)t[d].ls=del(t[d].ls,y,x);
    else t[d].rs=del(t[d].rs,y,x);
    return d;
}
int pre(int d)
{
    if (t[d].ls)
     {
        for (d=t[d].ls;t[d].rs;d=t[d].rs);
        return d;
     }
    while (d)
     {
        if (t[t[d].fa].rs==d) return t[d].fa;
        d=t[d].fa;
     }
    return -1;
}
int nxt(int d)
{
    if (t[d].rs)
     {
        for (d=t[d].rs;t[d].ls;d=t[d].ls);
        return d;
     }
    while (d)
     {
        if (t[t[d].fa].ls==d) return t[d].fa;
        d=t[d].fa;
     }
    return -1;
}
int det(ld x1,ld y1,ld x2,ld y2,ld x3,ld y3)
{
    ld res=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
    if (fabs(res)<=eps) return 0;
    if (res>0) return 1;
    else return -1;
}
int cr(int a,int b)
{
    if ((a==-1)||(b==-1)) return 0;
    a=t[a].id;b=t[b].id;
    if ((s[a].x1+eps>=min(s[b].x1,s[b].x2))&&(s[a].x1-eps<=max(s[b].x1,s[b].x2))
    &&(!det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x1,s[a].y1)))return 1;
    if ((s[a].x2+eps>=min(s[b].x1,s[b].x2))&&(s[a].x2-eps<=max(s[b].x1,s[b].x2))
    &&(!det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x2,s[a].y2)))return 1;
    if ((s[b].x1+eps>=min(s[a].x1,s[a].x2))&&(s[b].x1-eps<=max(s[a].x1,s[a].x2))
    &&(!det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x1,s[b].y1)))return 1;
    if ((s[b].x2+eps>=min(s[a].x1,s[a].x2))&&(s[b].x2-eps<=max(s[a].x1,s[a].x2))
    &&(!det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x2,s[b].y2)))return 1;
    if ((det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x1,s[b].y1)*
    det(s[a].x1,s[a].y1,s[a].x2,s[a].y2,s[b].x2,s[b].y2)<0)&&
    (det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x1,s[a].y1)*
    det(s[b].x1,s[b].y1,s[b].x2,s[b].y2,s[a].x2,s[a].y2)<0))return 1;
    else return 0;
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
     {
        scanf("%lf%lf%lf%lf",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2);
        rotate(s[i].x1,s[i].y1);rotate(s[i].x2,s[i].y2);
        if (s[i].x1>s[i].x2) swap(s[i].x1,s[i].x2),swap(s[i].y1,s[i].y2);
        s[i].k=(s[i].y2-s[i].y1)/(s[i].x2-s[i].x1);
        s[i].b=s[i].y1-s[i].k*s[i].x1;
        p[i].id=p[i+n].id=i;
        p[i].sg=1;p[i+n].sg=0;
        p[i].x=s[i].x1;p[i+n].x=s[i].x2;
     }
    sort(p,p+n*2,cmp);
    for (int i=0;i<n*2;i++)
     if (p[i].sg)
      {
        rt=ins(rt,s[p[i].id].y1,p[i].x,p[i].id);
        if (cr(date[p[i].id],pre(m)))
          {
            printf("YES
%d %d",p[i].id+1,t[pre(m)].id+1);
            return 0;
         }
        if (cr(date[p[i].id],nxt(m)))
         {
            printf("YES
%d %d",p[i].id+1,t[nxt(m)].id+1);
            return 0;
         }
     }
    else
     {
        if (cr(pre(date[p[i].id]),nxt(date[p[i].id])))
         {
            printf("YES
%d %d",t[pre(date[p[i].id])].id+1,
            t[nxt(date[p[i].id])].id+1);
            return 0;
         }
        rt=del(rt,s[p[i].id].y2,p[i].x);
     }
    puts("NO"); 
    return 0;
}

 

poj-1469-courses

poj-1469-COURSESCOURSESTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 24542 Accepted: 9557DescriptionConsideragroupofNstudentsandPcourses.Eachstudentvisitszero,on 查看详情

最小点覆盖,二分图最大匹配—poj1274poj1469poj1469

...match[v]=u就可以了三题的代码都是一样的,需要注意的是1469题是要求求最小点覆盖数,最小点覆盖数就等于最大匹配数。简 查看详情

poj——1469courses

                        COURSESTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 24192 Accepted: 9426DescriptionConsideragroupofNstudentsandPcourses.Eachstudentvisit 查看详情

poj1469courses

COURSESTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 21382 Accepted: 8408DescriptionConsideragroupofNstudentsandPcourses.Eachstudentvisitszero,oneormorethanoneco 查看详情

poj1469courses

COURSESTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 22584 Accepted: 8914DescriptionConsideragroupofNstudentsandPcourses.Eachstudentvisitszero,oneormorethanoneco 查看详情

poj1469courses(二分匹配模板)

题目链接:http://poj.org/problem?id=1469COURSESTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 17135 Accepted: 6730DescriptionConsideragroupofNstudentsandPcourses.Eachs 查看详情

poj1469courses题解

COURSESTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 21515 Accepted: 8455DescriptionConsideragroupofNstudentsandPcourses.Eachstudentvisitszero,oneormorethanoneco 查看详情

poj1469--courses(二分匹配)

COURSESTimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:23535 Accepted:9221DescriptionConsideragroupofNstudentsandPcourses.Eachstudentvisitszero,oneormorethanonecourses.Yourtaskistodeterm 查看详情

poj1469

匈牙利算法裸题#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cmath>#include<cstring>usingnamespacestd;constintN=300;intn,p,lin[N],cnt;boolm 查看详情

poj1469courses(代码片段)

http://poj.org/problem?id=1469网络流跑二分图模板题#include<iostream>#include<cstdio>#include<queue>#include<algorithm>#include<cmath>#include<ctime>#include<set>#includ 查看详情

poj1469courses二分图匹配

题目链接:​​http://poj.org/problem?id=1469​​​题意:有p门课,有n个学生,每门课有count个学生参加,现在每门课都要选一个代表出来,一个代表只能代表一门课,现在问你是否能对于每门课都选出一个代表出来解析:其实就是... 查看详情

洛谷——p1469找筷子

P1469找筷子题目描述经过一段时间的紧张筹备,电脑小组的“RP餐厅”终于开业了,这天,经理LXC接到了一个定餐大单,可把大家乐坏了!员工们齐心协力按要求准备好了套餐正准备派送时,突然碰到一个棘手的问题,筷子... 查看详情

蓝牙ble之da1469x的应用(代码片段)

文章目录0DA1469x系列资源简览1低功耗管理1.1进入休眠与退出休眠的总概览1.2FreeRTOS低功耗管理分析1.2.1Tickless具体实现1.2.2空闲任务具体实现1.3DA1469x低功耗管理分析1.3.1prvSystemSleep函数分析2看门狗系统2.1看门狗使用注意事项2.2看门... 查看详情

poj1469courses(二部图匹配)

                                 &n 查看详情

poj-1469courses[二分图匈牙利算法](代码片段)

COURSESTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 24919 Accepted: 9679DescriptionConsideragroupofNstudentsandPcourses.Eachstudentvisitszero,oneormorethanoneco 查看详情

poj1469courses二分图匹配匈牙利算法

...链接http://www.cnblogs.com/zhouzhendong/p/8232649.html题目传送门-POJ1469题意概括  在一个大矩阵中,有一些障碍点。  现在让你用1*2的小矩形覆盖非障碍点,要求不覆盖到障碍点并且不重复覆盖,问是否可以覆盖所有非障碍点。题解... 查看详情

洛谷p1469找筷子

 题目描述经过一段时间的紧张筹备,电脑小组的“RP餐厅”终于开业了,这天,经理LXC接到了一个定餐大单,可把大家乐坏了!员工们齐心协力按要求准备好了套餐正准备派送时,突然碰到一个棘手的问题,筷子!CX小... 查看详情

洛谷p1469找筷子题解(代码片段)

题目传送门先排序一遍,再一个一个判断是否有偶数个。注意for循环要i+=2。#include<bits/stdc++.h>usingnamespacestd;intn,a[10000010];intmain()scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);for(inti 查看详情