# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
932510 | n0sk1ll | Printed Circuit Board (CEOI12_circuit) | C++17 | 46 ms | 9616 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
#define int li
int x[100005],y[100005];
int ord[100005]; //order of the point
li dot(int a, int b, int c, int d)
{
return (li)a*d-(li)b*c;
}
struct mojsort
{
bool operator() (pair<pii,int> x, pair<pii,int> y)
{
return dot(x.xx.xx,x.xx.yy,y.xx.xx,y.xx.yy)>0;
}
};
int N;
int fwt[100005];
void add(int i, int x)
{
for (;i<=N;i+=(i&-i)) fwt[i]+=x;
}
int pre(int i)
{
int ret=0;
for (;i;i-=(i&-i)) ret+=fwt[i];
return ret;
}
main()
{
FAST;
int n; cin>>n;
ff(i,0,n) cin>>x[i]>>y[i];
vector<pair<li,int>> tacke;
ff(i,0,n) tacke.push_back({-((li)x[i]*x[i] + (li)y[i]*y[i]),i});
sort(all(tacke));
vector<pair<li,int>> duzi;
ff(i,0,n)
{
int j=(i+1)%n;
li d=max((li)x[i]*x[i]+(li)y[i]*y[i],(li)x[j]*x[j]+(li)y[j]*y[j]);
duzi.push_back({-d,i});
}
sort(all(duzi));
vector<pair<pii,int>> uglovi;
ff(i,0,n) uglovi.push_back({{x[i],y[i]},i});
sort(all(uglovi),mojsort());
int idx=0;
ff(i,0,n)
{
if (i==0 || dot(uglovi[i-1].xx.xx,uglovi[i-1].xx.yy,uglovi[i].xx.xx,uglovi[i].xx.yy)) ++idx;
ord[uglovi[i].yy]=idx;
}
N=idx;
vector<int> ans;
while (!tacke.empty() && !duzi.empty())
{
if (tacke.back().xx >= duzi.back().xx)
{
if (pre(ord[tacke.back().yy])==0)
{
ans.pb(tacke.back().yy+1);
}
tacke.popb();
}
else
{
int i=duzi.back().yy;
int j=(i+1)%n;
int l=ord[i];
int r=ord[j];
if (l>r) swap(l,r);
add(l,1);
add(r+1,-1);
duzi.popb();
}
}
sort(all(ans));
cout<<(int)ans.size()<<"\n";
for (auto it : ans) cout<<it<<" ";
}
//Note to self: Check for overflow
/*
11
7 6
4 4
3 2
1 3
9 9
13 4
8 1
6 4
9 5
8 3
11 5
*/
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |