哈哈我又来填坑了。



Description:

给你一个长度为 的连续折线 ,这些折线都是与坐标轴平行的。让你求这个直线形成的最小的环,如果不存在环就出输出这条折线的长度。



Solution:

首先这道题目是可以 过的。我们按顺序考虑折线的每一条线段,假设现在考虑第 条,那么我们只需要考虑它是否与前面的线段相交,如果相交,那么我们就找到了一个环,可以来更新答案,但是有可能这个环中包含了更小的环,但是事实上并没有关系,因为这些小的环已经在前面被算过了。


Code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

struct pot_
{
    int x,y;
    pot_() {x=y=0;}
    pot_(int a1,int a2) {x=a1,y=a2;}
}pot[4010];

int dist[4010]={0};

int N;
int ans=2e9;

struct pot_ operator -(struct pot_ a1,struct pot_ a2)
{return pot_(a1.x-a2.x,a1.y-a2.y);}

long long operator *(struct pot_ a1,struct pot_ a2)
{return (long long)a1.x*a2.y-(long long)a1.y*a2.x;}

bool check(struct pot_ a,struct pot_ b,struct pot_ c,struct pot_ d)
{return ((c-a)*(b-a))*((b-a)*(d-a))>=0 && ((a-c)*(d-c))*((d-c)*(b-c))>=0;}

struct pot_ getjd(struct pot_ a,struct pot_ b,struct pot_ c,struct pot_ d)
{
    if(a.x==b.x)
        return pot_(a.x,c.y);
    else return pot_(c.x,a.y);
}

int getdis(struct pot_ a1,struct pot_ a2)
{return abs(a1.x-a2.x)+abs(a1.y-a2.y);}

int main()
{
    freopen("sgu300.in","r",stdin);
    freopen("sgu300.out","w",stdout);
    cin>>N;
    scanf("%d%d",&pot[1].x,&pot[1].y);
    for(int i=2;i<=N;i++)
    {
        scanf("%d%d",&pot[i].x,&pot[i].y);
        dist[i]=dist[i-1]+getdis(pot[i-1],pot[i]);
        if(pot[i].x==pot[1].x && pot[i].y==pot[1].y) ans=min(ans,dist[i]);
        for(int j=2;j<i-2;j++)
        {
            if((pot[j-1].x==pot[j].x)==(pot[i-1].x==pot[i].x)) continue;
            if(check(pot[j-1],pot[j],pot[i-1],pot[i])==false) continue;
            struct pot_ jd=getjd(pot[j-1],pot[j],pot[i-1],pot[i]);
            int dis=dist[i-1]-dist[j-1]+getdis(jd,pot[i-1])-getdis(jd,pot[j-1]);
            ans=min(ans,dis);
        }
    }
    ans=min(ans,dist[N]);
    cout<<ans<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}