oj.uz

답안 #633366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633366 2022-08-22T08:25:18 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
30 / 100
 100 ms 10088 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
int n;
struct point
{
    int x,y,ang;
} v[100005],angle[100005];
bool comp(point a, point b)
{
    return a.y*b.x<a.x*b.y;
}
map<pii,int> nrm;
bool cmp(int a, int b)
{
    if(v[a].ang!=v[b].ang)
        return v[a].ang<v[b].ang;
    return v[a].y<v[b].y;
}
bool use[100005],spec[100005];
int aib[100005],times[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int cur=0;
bool iseq(point a, point b)
{
    return a.x==b.x&&a.y==b.y;
}
ll aria(point A, point B)
{
    ll rez=1LL*A.x*B.y-1LL*A.y*B.x;
    rez=abs(rez);
    return rez;
}
bool intersect(point A, point B, point C)
{
    if(iseq(A,C)||iseq(B,C))
        return 0;
 
    ll a1=B.y-A.y;
    ll b1=A.x-B.x;
    ll c1=-a1*A.x-b1*A.y;
 
    ll a2=C.y;
    ll b2=-C.x;
    ll c2=0;
 
    ld coef=a2*b1-a1*b2;
    if(coef==0)
        return 0;
    ld y=ld(-a2*c1)/coef;
    ld x=ld(-b2*y)/ld(a2);
    if(x>=min(A.x,B.x)&&x<=max(A.x,B.x)&&x<=C.x&&x>=0)
        if(y>=min(A.y,B.y)&&y<=max(A.y,B.y)&&y<=C.y&&y>=0)
            return 1;
    return 0;
}
bool checkgood(int i)
{
    if(cur==0)
        return 1;
    point a=v[cur];
    int lft=cur-1;
    if(lft<1)
        lft=n;
    point b=v[lft];
    if(intersect(a,b,v[i]))
        return 0;
    int rgt=cur+1;
    if(rgt>n)
        rgt=1;
    b=v[rgt];
    if(intersect(a,b,v[i]))
        return 0;
    return 1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x,y,0};
        int cmmdc=__gcd(x,y);
        x/=cmmdc;
        y/=cmmdc;
        angle[i]={x,y,0};
    }
    sort(angle+1,angle+n+1,comp);
   // cout<<'\n';
    for(int i=1;i<=n;i++)
    {
        pii a={angle[i].x,angle[i].y};
        nrm[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int cmmdc=__gcd(v[i].x,v[i].y);
        int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc;
        v[i].ang=nrm[{xa,ya}];
    }
    vector<int> ind;
    for(int i=1;i<=n;i++)
        ind.push_back(i);
    sort(ind.begin(),ind.end(),cmp);
    vector<int> sol;
    int nr=0;
    for(int i:ind)
    {
        nr++;
        bool good=checkgood(i);
        if(good)
        {
            cur=i;
            sol.push_back(i);
        }
    }
    sort(sol.begin(),sol.end());
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Compilation message

circuit.cpp: In function 'bool intersect(point, point, point)':
circuit.cpp:63:8: warning: unused variable 'c2' [-Wunused-variable]
   63 |     ll c2=0;
      |        ^~

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 4 ms 624 KB Output is correct
5 Incorrect 13 ms 1292 KB Output isn't correct
6 Incorrect 14 ms 1316 KB Output isn't correct
7 Incorrect 28 ms 2236 KB Output isn't correct
8 Incorrect 13 ms 1100 KB Output isn't correct
9 Correct 8 ms 980 KB Output is correct
10 Incorrect 14 ms 1236 KB Output isn't correct
11 Incorrect 15 ms 1340 KB Output isn't correct
12 Correct 20 ms 2180 KB Output is correct
13 Incorrect 39 ms 3236 KB Output isn't correct
14 Incorrect 39 ms 4044 KB Output isn't correct
15 Correct 52 ms 4880 KB Output is correct
16 Execution timed out 133 ms 9432 KB Time limit exceeded
17 Execution timed out 183 ms 10088 KB Time limit exceeded
18 Runtime error 59 ms 5060 KB Execution killed with signal 11
19 Runtime error 58 ms 5068 KB Execution killed with signal 11
20 Execution timed out 133 ms 8420 KB Time limit exceeded