[CF 512E] Fox And Polygon

作法：

這題我是看了這篇裡講的作法才會做的，詳細的作法在這篇comment裡，這裡大概講一下是怎麼做的。

我們能夠把任何對角線配置都轉換成其中一個端點在$1$的樣子就可以了，也就是所有對角線會是$1-3,1-4,...,1-(n-1)$（稱這樣子的對角線配置為標準型），因為這樣就可以從原本的對角線配置 -> 標準型 -> 目標對角線配置。而要讓對角線們成為標準型也很簡單，因為如果存在一條對角線$1-i$，但不存在$1-(i+1)$，那麼找一條對角線$1-j$使得$1-(i-1),...,1-(j-1)$都沒有對角線，則$i$一定和$j$有連線，只要把這條對角線換過來就可以讓其中一個端點在$1$的對角線增加一條，於是在$n-3$步以內就可以達到標準型了。


code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10 ;
struct P{int x,y;};
 
bool b[maxn][maxn] ;
int n ;
P change(int x,int y)
{
    int x2=-1,y2 ;
    for(int i=1;i<=n;i++) if(b[i][x]&&b[i][y])
    {
        if(x2==-1) x2=i ;
        else {y2=i ; break ;}
    }
    b[x][y]=b[y][x]=0 ;
    b[x2][y2]=b[y2][x2]=1 ;
    return (P){x2,y2} ;
}
 
void solve(const vector<P> &p,vector<P> &ret,bool inv)
{
    memset(b,0,sizeof(b)) ;
    vector<P> tmp ;
    for(int i=1;i<=n;i++) b[i][i%n+1]=b[i%n+1][i]=1 ;
    for(auto i : p) b[i.x][i.y]=b[i.y][i.x]=1 ;
    for(int i=2;i<n;)
    {
        if(b[1][i+1]) {i++ ; continue ;}
        int j ;
        for(j=i+1;!b[1][j];j++) ;
        P np=change(i,j) ;
        tmp.push_back(inv ? np : (P){i,j}) ;
    }
    if(inv) reverse(tmp.begin(),tmp.end()) ;
    for(auto i : tmp) ret.push_back(i) ;
}
 
vector<P> p,q,ans ;
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<=n-3;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        p.push_back((P){x,y}) ;
    }
    for(int i=1;i<=n-3;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        q.push_back((P){x,y}) ;
    }
    solve(p,ans,0) ; solve(q,ans,1) ;
    printf("%d\n",ans.size()) ;
    for(auto i : ans) printf("%d %d\n",i.x,i.y) ;
}