WA on #19 94 pts 求助,悬赏一个关注
查看原帖
WA on #19 94 pts 求助,悬赏一个关注
481527
AC_CSP楼主2023/3/1 09:39

record

# include <bits/stdc++.h>
using namespace std ;
const int N = 5e3 + 7 ;
const int M = 3e6 + 7 ;
int n ;
struct Edge {
	int nxt , v ;
} e[M]  ;
int in[N] ;
int cnt , h[N] ;
inline void Add_Edge ( int u , int v ) {
	e[++cnt] . nxt = h[u] , e[cnt] . v = v ;
	h[u] = cnt ;
}
struct Node {
	int x1 , y1 , x2 , y2 ;
} a[N] ;
inline int check ( int x , int y ) {
	bool flag = 0 ;
	if ( a[x] . x1 > a[y] . x1 ) swap ( x , y ) , flag = 1 ;
	if ( a[x] . x2 < a[y] . x1 ) return 0 ;
	if ( ! ( a[x] . x2 - a[x] . x1 ) ) {
		if ( a[x] . y1 < a[y] . y1 ) return flag ? 2 : 1 ;
		else return flag ? 1 : 2 ;
	}
	double tmp = a[x] . y1 + ( a[y] . x1 - a[x] . x1 ) * ( ( ( a[x] . y2 - a[x] . y1 ) * 1.0 / ( a[x] . x2 - a[x] . x1 ) ) );
	if ( a[y] . y1 < tmp ) return flag ? 1 : 2 ;
	else return flag ? 2 : 1 ; 
}
inline void Top_sort () {
	queue < int > q ;
	for ( int i = 1 ; i <= n ; i++ ) if ( ! in[i] ) q . push ( i ) ;
	while ( ! q . empty () ) {
		int u = q . front () ; q . pop () ;
		for ( int i = h[u] ; i ; i = e[i] . nxt ) {
			int v = e[i] . v ;
			if ( ! -- in[v] ) q . push ( v ) ;	
		}
		cout << u << " " ;
	}
}
int main () {
	ios :: sync_with_stdio ( false ) ;
	cin . tie ( 0 ) , cout . tie ( 0 ) ;
	cin >> n ;
	for ( int i = 1 ; i <= n ; i++ ) {
		int x1 , y1 , x2 , y2 ;
		cin >> x1 >> y1 >> x2 >> y2 ;
		if ( x1 > x2 ) swap ( x1 , x2 ) , swap ( y1 , y2 ) ;
		a[i] . x1 = x1 , a[i] . x2 = x2 , a[i] . y1 = y1 , a[i] . y2 = y2 ; 
	}
	for ( int i = 1 ; i <= n ; i++ ) {
		for ( int j = i + 1 ; j <= n ; j++ ) {
			int opt = check ( i , j ) ;
			if ( opt == 1 ) Add_Edge ( i , j ) , in[j] ++ ;
			if ( opt == 2 ) Add_Edge ( j , i ) , in[i] ++ ;
			// cout << i << " " << j << " " << opt << "\n" ;
		}
	}
	Top_sort () ;
	return 0 ;
}

2023/3/1 09:39
加载中...